Tutorial — Hàng cột

Điều kiện cảnh quan đòi hỏi dãy chiều cao không được phép tăng lên sau khi đã giảm, tức là dãy kết quả phải có dạng đơn đỉnh với một vị trí cao nhất. Khi đã chọn một vị trí làm đỉnh, chiều cao các cây cột sẽ giảm dần hoặc giữ nguyên khi đi xa dần khỏi đỉnh về hai phía.

Nếu cố định vị trí đỉnh $p$, chiều cao tối ưu của các cây cột ở hai phía hoàn toàn độc lập với nhau. Tại mỗi phía, việc tối đa hóa chiều cao dẫn đến việc mỗi phần tử là giá trị nhỏ nhất của các giới hạn tính từ vị trí đó hướng về đỉnh.

Để tính nhanh tổng chiều cao hai phía cho toàn bộ $n$ vị trí mà không mất $O(n^2)$, hãy sử dụng ngăn xếp đơn điệu (monotonic stack) để tìm phần tử nhỏ hơn gần nhất và thiết lập công thức quy hoạch động tính tổng tiền tố và hậu tố trong thời gian $O(n)$.