1 条题解

  • 0
    @ 2023-10-18 10:01:02

    C++ :

    #include<bits/stdc++.h>
    using namespace std;
    const int N=300010;
    int q[N],s[N];
    int main()
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            s[i]=s[i-1]+x; //计算前缀和
        }
        int hh=0,tt=-1; //清空数组
        q[++tt]=0; //s[0]
        int res=-2e9;
        for(int i=1;i<=n;i++)
        {
            while(hh<=tt&&i-q[hh]>m) hh++; //队列中有元素,且在加入了当前元素以后会超过窗口
            res=max(res,s[i]-s[q[hh]]); //以当前元素结尾的长度不超过m的子序列和
            while(hh<=tt&&s[q[tt]]>=s[i]) tt--; //更新单调队列
            q[++tt]=i; //将当前元素加入队列
        }
        cout<<res;
        return 0;
    }
    
    
    • 1

    信息

    ID
    773
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者