网址：https://www.luogu.org/problem/P1714
给出一个有$n$个数的序列，求出区间长度$k \leq m$的和的最大值。（$n\leq 5e5，m \leq 5e2$）。
本题需要求$max(sum[i]-sum[j],(0 \leq i-j<m))$，直接暴力求会TLE，所以我们需要用数据结构优化，因为是求$max(sum[i]-sum[j],(0 \leq i-j<m))$，即$sum[i]-min(sum[j],j \in [i-m+1，i])$，故使用单调递增队列维护最小值即可。
AC代码：
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
int num[500005];
long long sum[500005];
struct node
{
long long sum;
int pos;
node(long long a,int b)
{
sum=a,pos=b;
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>num[i],sum[i]=sum[i-1]+num[i];
long long ans=-0x3f3f3f3f;
deque<node>maxq;
maxq.push_back(node(sum[0],0));
for(int i=1;i<=n;++i)
{
ans=max(ans,sum[i]-maxq.front().sum);
while(!maxq.empty()&&maxq.back().sum>=sum[i])
maxq.pop_back();
maxq.push_back(node(sum[i],i));
while(maxq.front().pos<i-m+1)
maxq.pop_front();
}
cout<<ans<<endl;
return 0;
}
原文：https://www.cnblogs.com/Aya-Uchida/p/11300611.html