Tutorial — Terrain Route

Ta nhận xét rằng nếu sắp xếp các cao độ tăng dần, cặp hai phần tử kề nhau bất kỳ có hiệu nhỏ nhất chính là ứng viên tối ưu để đặt vào vị trí đầu tiên và cuối cùng của tuyến đường.

Với $n > 2$, nếu muốn giữ nguyên hiệu nhỏ nhất giữa cột mốc đầu và cột mốc cuối, tuyến đường không thể hoàn toàn không giảm mà bắt buộc phải có ít nhất một bước giảm độ cao, tức độ thử thách không thể vượt quá $n - 2$.

Sau khi sắp xếp mảng và chọn được cặp kề nhau $(a_i, a_{i+1})$ có hiệu nhỏ nhất, ta chia mảng thành hai đoạn tăng dần và đặt $a_{i+1}$ ở đầu tuyến đường, tiếp nối đến $a_{n-1}$, rồi quay lại từ $a_0$ đến $a_i$ ở cuối tuyến đường.