输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 1。

输入格式
第一行输入两个整数 n,m。

第二行输入 n 个数，代表长度为 n 的整数序列。

同一行数之间用空格隔开。

输出格式
输出一个整数，代表该序列的最大子序和。

数据范围
1≤n,m≤300000

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

参考答案

#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=300100;
deque<long long> q;
long long n,m,l,r,s[N],a[N],ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    fir(i,1,n)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    fir(i,1,n)
    {
        while(q.size() && q.front()<i-m)//如果队头已经无法满足区间长度小于m的话,那么弹出
            q.pop_front();//队头不满足,不需要,弹出.
        ans=max(ans,s[i]-s[q.front()]);//取当前最优值
        while(q.size() && s[q.back()]>=s[i])//如果说队尾大于当前值的话.
            q.pop_back();//不需要,弹出
        q.push_back(i);//将i放入队尾.
    }
    cout<<ans;
    return 0;
}