Nguồn: CSES

Gọi ~s(i)~ là tổng tiền tố ~x_1+x_2+...+x_i~. Sử dụng hàm này, ta có thể tính tổng của bất kỳ đoạn con nào như sau:

$$\displaystyle x_j+x_{j+1}+...x_i=s(i)-s(j-1)$$

Để giải bài toán, ta duyệt qua mảng và duy trì một multiset chứa tất cả các tổng tiền tố ~s(k)~ thỏa mãn: ~i-b\le k \le i-a~, trong đó ~i~ là vị trí hiện tại. Khi đó, tổng lớn nhất của một đoạn con kết thúc tại vị trí ~i~ là ~s(i)-s(k')~ với ~s(k')~ là tổng tiền tố nhỏ nhất trong multiset. Độ phức tạp: ~O(n.log(n))~.

Ta cũng có thể xây dựng một lời giải hiệu quả hơn bằng cách sử dụng thuật toán tìm giá trị nhỏ nhất trên cửa sổ trượt trong thời gian tuyến tính, thay cho multiset. Ý tưởng là duy trì một dãy tăng dần các giá trị nằm trong cửa sổ hiện tại. Cách này sử dụng cấu trúc dữ liệu deque và có độ phức tạp ~O(n)~.

Tham khảo Bài toán tìm max-min trong đoạn tịnh tiến