撰写描述
输入一个长度为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,m<=300000）
第二行有n个数，要求在n个数找到最大子序和
输出格式
一个数，数出他们的最大子序和
样例输入
6 4 1 -3 5 1 -2 3
样例输出
7
题解：对于区间和题目，一般转化为前缀数组来解。
对于前缀数组来说，如果有s[k]>=s[j]&&k<j，那么s[k]肯定不会是最优解，可以直接被pass，所以最终的解之间的前缀和序列一定是递增的。
另外，前缀和本身就带有“连续”的性质，所以不需要判断连续，只需要枚举右端点i，更新所有符合条件的区间和。
- 判断队头是否超处m的范围，是则出队。
- 以此状态下最优值更新ans。
- 不断删除队尾，直到对应s值小于s[i]（满足递增）。
因为每个元素最多出入队一次，所以是O(n)级别的算法。
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
using namespace std;
const int maxn=1e6+10;
int a[maxn];
ll s[maxn];
int q[maxn];
template <class T>
inline bool scan_d(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
inline void outt(int x) {
if(x>9) outt(x/10);
putchar(x%10+'0');
}
int n,m;
int main(){
while(scanf("%d%d", &n,&m)==2){
s[0]=0;
rep(i,1,n){
// scan_d(a[i]);
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int l=1,r=1;
ll ans=-INF;
q[1]=0;
rep(i,1,n){
while(l<=r&&i-q[l]>m)l++;
ans=max(ans,s[i]-s[q[l]]);
while(l<=r&&s[i]<=s[q[r]])r--;//这里<=才能获得更高的宽容度
q[++r]=i;
}
cout<<ans;
}
return 0;
}