Bài toán cần các giá trị tối ưu cho mọi số lượng chọn trên một đường thẳng, không chọn hai vị trí kề nhau.

Dùng tham lam có hoàn tác:

• Đưa mọi vị trí vào heap theo điểm hiện tại.
• Mỗi lượt chọn vị trí có điểm lớn nhất còn hiệu lực, cộng vào đáp án.
• Hai vị trí kề nó không thể cùng tồn tại trong cấu hình hiện tại nên bị xóa khỏi danh sách liên kết.
• Gộp ba vị trí trái, giữa, phải thành một vị trí mới có giá trị ~a_L+a_R-a_U~. Nếu vị trí gộp được chọn lại ở lượt sau, điều đó tương đương hoàn tác chọn ~U~ và chuyển sang chọn hai bên.

Dùng mảng liên kết trái/phải để xóa và gộp trong ~O(\log n)~ mỗi lượt. Tổng độ phức tạp ~O(n\log n)~.