描述

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

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

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

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

输入格式

第一行两个数n,m

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

输出格式

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

测试样例1

输入

6 4 

1 -3 5 1 -2 3

输出

7

备注

数据范围：

100%满足n,m<=300000

 

 

用单调队列维护从开始到[i]范围内的最小值，总和减去该最小值，就是最大序列和。

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int mxn=310000; 7 int f[mxn],p[mxn]; 8 int a; 9 int ans=0,sum=0;10 int n,m;11 int main(){12     scanf("%d%d",&n,&m);13     int i,j;14     int hd=1,tl=2;15     for(i=1;i<=n;i++){16         scanf("%d",&a);17         sum+=a;18         while(f[tl-1]>=sum && tl>hd)tl--;//处理队尾，维护队列单调19         f[tl]=sum;20         p[tl]=i;21         tl++;22         while(i-p[hd]>m)hd++;//检查队头元素是否符合要求长度 23         if(sum-f[hd]>ans)ans=sum-f[hd];//更新最优解 24     }25     printf("%d\n",ans);26     return 0;27 }