解题思路
??枚举右端点,利用前缀和计算\(max(pre[r] - min(pre[l])), l \epsilon [r-m,r-1]\)。所以关键就是如何在范围内找到\(min(pre[l])\),对于范围内的前缀和来说,如果靠右的前缀和比靠左的小,那就肯定用不到他,而如果比靠左的大,如果左边的超出了范围,那么它就可能是一个新的最小值,所以队列里的数就有单调性,可以用单调队列来优化。
代码
const int maxn = 3e5+10;
int n, m;
ll pre[maxn];
deque<int> dq;
int main() {
scanf("%d%d",&n,&m);
for (int i = 1; i<=n; ++i) {
scanf("%lld",&pre[i]);
pre[i] += pre[i-1];
}
ll ans = pre[1];
for (int i = 2; i<=n; ++i) {
if (!dq.empty() && dq.front()<i-m) dq.pop_front();
while (!dq.empty() && pre[dq.back()] >= pre[i-1]) dq.pop_back();
dq.push_back(i-1);
ans = max(ans, pre[i]-pre[dq.front()]);
}
printf("%lld\n",ans);
return 0;
}