Nguồn: Thầy Thuận, Tập huấn đội tuyển Quảng Ninh, HÀ NỘI, 15/11/2016
Ông vua ở một vương quốc nọ có kho vàng nằm trên một đường thẳng được đánh số theo thứ tự là , trong đó kho vàng có trữ lượng vàng là ( là số nguyên không âm) và đặt tại toạ độ . Nhà vua mở cuộc thi tài cho những người tìm vàng xem ai là người có thể lựa chọn được dãy các kho vàng có tổng trữ lượng lớn nhất với điều kiện khoảng cách giữa kho liên tiếp trong dãy các kho được chọn ra phải lớn hơn hoặc bằng và nhỏ hơn hoặc bằng , nghĩa là, nếu dãy kho được chọn là , thì ta phải có .
Dữ liệu vào:
Dòng đầu ghi giá trị cách nhau bởi dấu cách ;
Dòng thứ hai ghi giá trị nguyên cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra duy nhất một số là tổng trữ lượng của các kho vàng được lựa chọn.
Ví dụ:
Dữ liệu vào:
6 2 2
3 5 9 6 7 4
Dữ liệu ra:
19
Giải thích:
Phương án tối ưu là lựa chọn dãy kho vàng và với tổng dự trữ là .
