题目描述
链接:https://ac.nowcoder.com/acm/contest/1006/D
来源:牛客网

输入一个长度为n的整数序列,从中找出一段不超过m的连续子序列,使得整个序列的和最大。
例如 1,-3,5,1,-2,3
当m=4时,S=5+1-2+3=7
当m=2或m=3时,S=5+1=6

这个题既然出现在队列的题里面了,那我们就简简单单的用一个单调队列来解决。

分析
看到区间二字,我们首先想到前缀和数组,将原序列转化为前缀和数组后,我们要求的一段序列和,也就成了前缀和数组S[i]在[l,r]上的和,即s[r]-s[l-1];
也就是说,我们要在前缀和数组上找到两个点x,y,使得s[x]-s[y]最大,并且x-y<=m。
但又有一个问题,如果我们直接暴力枚举x,y,那必然超时,这个时候队列的作用就体现了,我们可以先固定右端点i,再去寻找一个左端点j,使得s[j]值最小,并且我们还可以确定j的范围[i-m,i-1],然后自己手捏数据找规律,我们可以发现 最优决策集合一定是一个下标位置递增,对应前缀和数组值也递增的序列

好,理论有了,动手实践。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize(3)//手动开O3,你值得拥有

int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f; 
}

const int N=3e5+10;
int n,m;
int q[N];
int s[N];

signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        s[i]=read();
        s[i]+=s[i-1];//变为前缀和 
    }
    int l=1,r=1;//队头,队尾 
    int ans=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        if(i-q[l]>m) l++;//区间长度大于m,出队 
        ans=max(ans,s[i]-s[q[l]]);//寻找最优解 
        while(l<=r&&s[q[r]]>=s[i]) r--;//如果队尾不满足单调递增,出队 
        q[++r]=i;//把i当成新的决策点 
    }
    cout<<ans;
    return 0;
}