Nhận xét: Một nhóm các đơn hàng liên tiếp chỉ gồm tối đa từ ~1~ tới ~19~ đơn hàng, vì nếu nhóm gồm ít nhất ~20~ đơn hàng, thì việc tách nhóm thành ~2~ nhóm sẽ luôn tối ưu hơn.

Gọi ~dp[i]~ là tổng giá trị lớn nhất của các đơn hàng được miễn phí khi nhóm hết các đơn từ ~1~ tới ~i~. Ta có công thức QHĐ đơn giản sau:

~dp[i] = \max\bigl(dp[i], dp[i - 1] \bigr)~

~dp[i] = \max\bigl(dp[i], dp[i - j] + \min(a_{i - j + 1}, a_{i - j + 2}, \cdots, a_i) \bigr) [j=10 \rightarrow 19]~

Kết quả của bài toán là: ~\sum_{i=1}^{n} a_i - dp[n]~.

Độ phức tạp là ~\mathcal{O}(N)~.