Maximum Subarray Sum II

题目描述

Given an array of n integers, your task is to find the maximum sum of values in a contiguous subarray with length between a and b.

输入

The first input line has three integers n, a and b: the size of the array and the minimum and maximum subarray length.
The second line has n integers x1,x2,...,xn: the array values.
Constraints
1≤n≤
1≤a≤b≤n
≤xi≤

输出

Print one integer: the maximum subarray sum.

样例输入

8 1 2
-1 3 -2 5 3 -5 2 2

样例输出

8

思路分析

1.读取数组x，前缀和处理

2.遍历数组x，下标从a到n，双端队列维护滑动窗口。

该窗口存储的是前缀和数组的下标，并确保队列中的下标对应的前缀和值单调递增。这样，队列的队首元素就是当前窗口内前缀和最小的下标。

队列元素k对应的前缀和x[k]尽可能小，以k+1为起点的子区间和才会尽可能大。

如果无法保证队列中的下标对应的前缀和值单调递增，也就无法保证队首是最优起点，时间复杂度也会大大增加。

解析样例：

i=1时，把0添加至队尾，更新ans=max(-2147483648,-1);

i=2时，弹出队尾元素0，把1添加至队尾，更新ans=max(-1,3);

i=3时，把2添加至队尾，ans仍为3;

i=4时，弹出队尾元素2，把3添加至队尾，弹出队首元素1，更新ans=max(3,5);

i=5时，把4添加至队尾，更新ans=max(5,8);

i=6时，把5添加至队尾，弹出队首元素3，ans仍为8;

i=7时，弹出队尾元素5和4，把6添加至队尾，ans仍为8;

i=8时，把7添加至队尾，ans仍为8。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a,b;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>a>>b;
    vector<ll>x(n+1,0);
    for(ll i=1;i<=n;i++){
        cin>>x[i];
        x[i]+=x[i-1];
    }
    deque<ll>q;
    ll ans=LONG_MIN;
    for(ll i=a;i<=n;i++){
        while(!q.empty()&&x[q.back()]>=x[i-a]){
            q.pop_back();
        }
        q.push_back(i-a);
        while(!q.empty()&&q.front()<i-b){
            q.pop_front();
        }
        if(!q.empty()){
            ans=max(ans,x[i]-x[q.front()]);
        }
    }
    cout<<ans;
    return 0;
}