Nhờ giúp đỡ thuật toán bài tìm đoạn con liên tiếp có tổng lớn nhất

[cipheran93 (Cipher An)]

Cho dãy n số nguyên a₁, a₂, …, a_n và số nguyên dương k.
Yêu cầu: Tìm đoạn con liên tiếp gồm ≥ k số nguyên trong dãy, sao cho tổng các số nguyên thuộc đoạn là lớn nhất.
Dữ liệu: Vào từ file văn bản SUBSEQ.INP

• Dòng 1: chứa hai số nguyên n, k (1 ≤ k ≤ n ≤ 10⁶)
• n dòng tiếp theo, dòng thứ i chứa một số nguyên a_i (|a_i| ≤ 1000)

Kết quả: Ghi file văn bản SUBSEQ.OUT một số nguyên là tổng các giá trị đoạn con tìm được theo yêu cầu.

Ví dụ:
SUBSEQ.INP

8 3
-20
90
-30
-20
80
-70
-60
125

SUBSEQ.OUT

120

Ràng buộc:

• Subtask 1:
• Subtask 2:
• Subtask 3: 20% số test n ≤ 10⁵
• Subtask 4: 20% số test n ≤ 10⁶

[rogp10]

Gợi ý: Xét trường hợp suy biến k = 0 và k = 1.

Gợi ý 2

Bây giờ khi bạn đang ở vị trí thứ i thì nên kéo dài mảng con đang giữ tới i luôn, hay chọn mảng con kết thúc tại i?

O(1) mem và O(n) time.