最大子序和（单调队列）

r囧r小猫 2021-10-19 03:58 278阅读 0赞

[https://www.acwing.com/problem/content/137/][https_www.acwing.com_problem_content_137]

我们知道不加长度限制的最大子序列和可以用贪心轻松解决。然而这道题中给子序列增加了一个最大长度为m的限制，那么贪心就不正确了。

首先将区间和转化为前缀和之差，那么\[l，r\]的区间和应该是S\[r\]-S\[l-1\]。那么该问题就转化为找到x，y（x<y且y-x<=m）使得S\[y\]-S\[x\]最大。

如果y固定，那么S\[x\]自然是越小越好，那么如果我们能维护一个单调递增的队列，这个问题就可以解决了。

使用单调队列，依次push编号入队，在每个编号i即将入队时进行一下决策：

1.如果i-队首编号>m，则弹出队首元素。

2.经过1步骤之后，队首元素就是对于i的最优左端点。若队列为空，则i的左端点就是自身。

3.循环弹出S值大于S\[i\]的队尾元素。

4.将i压入队尾。

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <deque>
    using namespace std;
    typedef long long LL;
    deque<LL> dq;
    int n,m;
    LL sum[300010];
    
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%lld",&sum[i]);
        for(int i=1;i<=n;i++) sum[i]=sum[i]+sum[i-1];
        LL ans=-1e18;
        dq.push_back(0);
        for(int i=1;i<=n;i++)
        {
            while(!dq.empty()&&dq.front()<i-m) dq.pop_front();
            if(dq.empty()) ans=max(ans,sum[i]);
            else ans=max(ans,sum[i]-sum[dq.front()]);
            while(!dq.empty()&&sum[dq.back()]>=sum[i]) dq.pop_back();
            dq.push_back(i);
        }
        printf("%lld\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/BakaCirno/p/11297340.html

[https_www.acwing.com_problem_content_137]: https://www.acwing.com/problem/content/137/