输入

6 4 
1 -3 5 1 -2 3

输出

7

/*单调队列优化dp单调队列维护的是前缀和的递增序列更新答案的时候从对首开始找第一个区间在m范围内的f[i]表示到第i个数的不超过m的最大连续子段和,sum[i]表示i的前缀和f[i]=max(sum[i]-sum[k])（i=> k >=i-m）,所以要找最小的sum[k]，因此用单调队列。 */#include<iostream>#include<cstdio>  using namespace std;int n,m,tot,head,tail,x,k;    struct node{      int v,u; //v代表值，u代表下标用来判断是否超过m }q[100001];    int main()  {      scanf("%d%d",&n,&m);      scanf("%d",&tot);//第一个元素      head=1;tail=2;      q[head].v=tot;q[head].u=1;      k=tot;    for(int i=2;i<=n;i++)      {          scanf("%d",&x);          tot+=x;          while(q[tail-1].v>=tot && tail-1>=head) tail--;//队列中只有一个元素且比当前和大，更新         q[tail].v=tot;          q[tail].u=i;//记录下标          tail++;        if(i-q[head].u>m) head++;//确定区间m         if(tot-q[head].v>k) k=tot-q[head].v;  //更新答案     }      printf("%d\n",k);      return 0; }