描述
输入一个长度为n的整数序列，从中找出一段不超过M的连续子序列，使得整个序列的和最大。
例如 1，-3,5,1，-2,3
当m=4时，S=5+1-2+3=7
当m=2或m=3时，S=5+1=6
例如 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个数找到最大子序和
第二行有n个数，要求在n个数找到最大子序和
输出格式
一个数，数出他们的最大子序和
测试样例1
输入
6 4
1 -3 5 1 -2 3
输出
7
备注
数据范围：
100%满足n,m<=300000
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
第一次写单调队列呐~ 感觉好高端~
不得不说这个和openjudge 1481 Maximum sum 好像
//tyvj 1305 [单调队列]
#include<cstdio>int n,m,tot,head,tail,x,k;struct node{int v,u; //值和下标
}kk[100001];int main()
{scanf("%d%d",&n,&m);scanf("%d",&tot);head=1;tail=2;kk[head].v=tot;kk[head].u=1;k=tot;for(int i=2;i<=n;i++){scanf("%d",&x);tot+=x;while(kk[tail-1].v>=tot && tail-1>=head) tail--; //>=，写成 > 会出错 kk[tail].v=tot;kk[tail].u=i;tail++; //先记后加 if(i-kk[head].u>m) head++;if(tot-kk[head].v>k) k=tot-kk[head].v;}printf("%d\n",k);
}