AcWing 652. 切蛋糕(Python3)
原题链接
简单
作者:
跂未
,
2024-03-17 21:48:30
,
所有人可见
,
阅读 10
from collections import deque
n, m = map(int, input().split())
a = list(map(int, input().split()))
s = [0] * (n + 1)
qu = deque()
ans = 0
# 对原数组求前缀和
for i in range(1, n + 1):
s[i] = s[i - 1] + a[i - 1]
for i in range(n + 1):
# 控制队列内的元素<=m
while qu and qu[0] < i - m:
qu.popleft()
# 维护一个单调递增的队列,这样就可以使
# 队头元素对应的值最小
while qu and s[i] < s[qu[-1]]:
qu.pop()
# 求一端序列的和的公式为s[r] - s[l - 1]
# 在这里将s[i]看成队列内的元素,则s[q[0]]就相当于s[l-1]
if qu:
ans = max(ans, s[i] - s[qu[0]])
qu.append(i)
print(ans)