AcWing 135. 最大子序和 转换为滑动窗口极值求解
原题链接
简单
作者:
皓首不倦
,
2020-07-29 13:25:51
,
所有人可见
,
阅读 948
'''
首先求序列的前缀和序列s, 将问题转换一下,以arr[i]结尾的长度不超过m的和最大
的连续子序列就是在s[i]前面的m个数中找最小的一个s[k],s[i]-s[k]就是以arr[i]
结尾的长度不超过m的和最大的连续子序列的和,其实问题就转换成了单调队列求滑动
窗口极值问题
'''
from collections import deque
n, m = map(int, input().split())
arr = list(map(int, input().split()))
pre_sum = [val for val in arr]
for i in range(1, n):
pre_sum[i] += pre_sum[i-1]
ans = -0x7fffffff
que = deque()
for idx, val in enumerate(pre_sum):
if idx <= m-1:
if len(que) > 0:
min_val = min(0, que[0][1])
else:
min_val = 0
else:
min_val = que[0][1]
ans = max(ans, val - min_val)
while len(que) > 0 and idx - que[0][0] >= m:
que.popleft()
while len(que) > 0 and que[-1][1] >= val:
que.pop()
que.append((idx, val))
print(ans)