Tutorial — Hành Trình Chọn Trạm

Với một bộ ba chỉ số được chọn $i_1 < i_2 < i_3$, hãy xét xem độ dài đoạn $[l, r]$ nhỏ nhất chứa cả ba trạm này là bao nhiêu.

Bằng cách chọn $l = i_1$ và $r = i_3$, biểu thức $a_{i_1} + a_{i_2} + a_{i_3} - (r - l)$ có thể viết lại thành $(a_{i_1} + i_1) + a_{i_2} + (a_{i_3} - i_3)$.

Nếu ta cố định vị trí ở giữa $i_2 = j$, các vị trí $i_1 < j$ và $i_3 > j$ có thể được tìm một cách độc lập để lần lượt tối đa hóa $(a_{i_1} + i_1)$ và $(a_{i_3} - i_3)$.

Sử dụng mảng tiền tố $P[j] = \max_{1 \le i \le j} (a_i + i)$ và mảng hậu tố $S[j] = \max_{j \le k \le n} (a_k - k)$ để tính kết quả lớn nhất tại mỗi vị trí $j$ trung gian trong thời gian $O(1)$.