AcWing 单调队列优化DP相关问题 135. 最大子序和

import sys
sys.stdin = open('data.txt', 'r')'''
首先求序列的前缀和序列s, 将问题转换一下，以arr[i]结尾的长度不超过m的和最大
的连续子序列就是在s[i]前面的m个数中找最小的一个s[k]，s[i]-s[k]就是以arr[i]
结尾的长度不超过m的和最大的连续子序列的和，其实问题就转换成了单调队列求滑动
窗口极值问题'''from collections import dequen, 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 = 0else: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)