最大子序和

题目 最大子序和

image-204e7121

思路分析

首先很容易想到前缀和

image-a3a8821a

问题转变成对于每个r找一个窗口中的最小的l-1

可以挖掘出一些性质

如果-2加入 那它左边的1就绝对不会是答案 因为1本身就在左边 会先出队 所以1可以删除

而-2右边的3有可能作为答案 因为-2在左边 它会先从窗口划出去

所以这个队列里的数应该是单调递增的

我们要的答案就是队头的那个最小的数

单调队列 模版中的找最小值

image-3ec719b8

注意一个问题 5的要找的答案应该是那个-2 （s[r]-s[l-1]）

窗口在5加入之前得出答案 而不是5加入后得到答案

所以先求res再插入5 对队列做维护

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=300010;

int q[N];

LL s[N];

int n,m;

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++){

        int x;

        cin>>x;

        s[i]=s[i-1]+x;

    }

    int hh=0,tt=0;

    q[0]=0;

    LL res=INT_MIN;

    for(int i=1;i<=n;i++){

        if(hh<=tt && i-q[hh]>m)

            hh++;

        //注意这个位置 当前数的左边最小值 应该是不包含该数的左边m个数里找（在队头） 所以在插入之前更新答案

        res=max(s[i]-s[q[hh]],res);

        while(hh<=tt && s[i]<=s[q[tt]])

            tt--;

        q[++tt]=i;

    }

    cout<<res<<endl;

    return 0;

}

同类题型

视频讲解

⬅️ 子矩阵 🏠 00-刷题理模型 ➡️ 滑动窗口的最大值