单调上升队列

先对序列求前缀和, 求连续子序列的区间和等价于前缀和终点与起点的差值.
队列保存的是连续子序列的起点.
其他相同情况下, 起点的值是越小越好,
其他相同情况下, 起点的位置是越靠右越好.因为越靠右, 连续子序列的区间长度越小, 之后的潜力越大.
对于两个元素a和b, a在左边, b在右边, 如果a >= b, 那么a应该立即被排除出去, 因为a相比b, 在值和位置上, 都占了劣势.
因此, 队列保存的起点应该是一个单调上升的序列, 单调上升意味着每个元素是帕累托最优的, 要么在位置上占优, 要么在值上占优.

时间复杂度

对于任意个元素, 入队一次, 出队一次或0次, 因此, 时间复杂度是O(N)

Python 代码

from collections import deque

n, m = map(int, input().split())
A = list(map(int, input().split()))
A = [0] + A
for i in range(1, n + 1):
    A[i] += A[i - 1]

ans = float("-inf")
L = deque()
for i, e in enumerate(A):
    while L and i - L[0] > m:
        L.popleft()
    if L:
        ans = max(ans, e - A[L[0]])
    while L and A[L[-1]] >= e:
        L.pop()
    L.append(i)
print(ans)