AcWing 135. Maximum subsequence sum

AcWing 135. The largest subsequence and

Ideas

• Computing intervals and problems are generally transformed into prefixes and problems , So the original problem can be transformed into finding two positions $l$ And $r$ bring $a[r]-a[l-1]$ The biggest and $r-l+1<=m$.
• First, let's enumerate $i$, When $i$ When fixed as the right endpoint , The problem turns into finding a left endpoint $j$,$j$ The scope is $[i-m+1,i-1]$, also $a[j-1]$ Minimum （ Because to make $i$ To $j$ And $a[i]-a[j-1]$ Maximum ）.
• At this time, it is easy to think of monotonous queues （$que$ The subscript queue ）： The value at the end of the team $a[que[t-1]]$ Greater than or equal to $a[i]$ You can pop up the tail of the team , because i The subscript is larger （ It's not easy to be eliminated ） And the value is smaller . Then the value of the team leader must be the smallest , What we should pay attention to here is , When updating the right endpoint, you need to judge whether the queue header pops up （ keep $i-que[t-1]+1<=m$ ）.

#include<iostream>
#define int long long
using namespace std;
const int N = 300010;
int a[N],que[N],h,t;
signed main(){
    
    int n,m; cin>>n>>m;
    for(int i = 1; i <= n; i++) {
    
        int x; cin>>x;
        a[i] = a[i-1] + x;
    }
    int res = -0x3f3f3f3f;
    h = 0,t = 1;
    for(int i = 1; i <= n; i++){
    
        if(h < t && i - que[h] > m) h++;
        res = max(res, a[i] - a[que[h]]);
        while(h < t && a[que[t-1]] >= a[i]) t--;
        que[t++] = i;
    }
    cout<<res;
    return 0;
}

Reference resources

https://www.acwing.com/solution/content/28015/