Description

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

例如 1，-3,5,1，-2,3

当m=4时，S=5+1-2+3=7

当m=2或m=3时，S=5+1=6

Input

第一行两个数n,m

第二行有n个数，要求在n个数找到最大子序和

Output

一个数，数出他们的最大子序和

Sample Input

6 4

1 -3 5 1 -2 3

Sample Output

7

Hint

数据范围：

100%满足n,m<=300000

 

/*    区间和→两个前缀和相减    求出s[i]表示序列前i项的和，则区间[i,j]中数的和=s[j]-s[i-1]。    问题变为找出两个位置i,j，使得s[j]-s[i]最大并且j-i<=m。    枚举右端点i，若i固定，问题变为找到j∈[i-m,i-1]使得s[j]最小    若k
       
        
         =s[j]，则在i及i之后的扫描中，k永远不会成为最优决策。    可以维护一个下标位置递增、对应前缀和的值递增的队列，当i变化时及时判断队头是否超出m的范围，取队头为最优解，然后在队尾插入新的i并维护单调性，时间复杂度O(N)。*/#include
         
          #include
          
           using namespace std;int a[300010];struct node{    int sum,xb;}q[300010];int head=1,tail=0,ans=0;int main(){    int n,m;    cin>>n>>m;    for (int i=1;i<=n;i++) cin>>a[i];    for (int i=1;i<=n;i++) a[i]=a[i]+a[i-1];    q[++tail].sum=a[1];q[tail].xb=1;ans=a[1];//从2开始循环，所以ans初值赋为a[1]     for (int i=2;i<=n;i++)    {        while (q[tail].sum>=a[i] && tail>=head) tail--;//维护单调性         q[++tail].xb=i; q[tail].sum=a[i];        if (i-m>q[head].xb) head++;        ans=max(ans,a[i]-q[head].sum);    }    cout<