最大子序和

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=1e6+10;
int read()
{
    int x=0,f=0,c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x; 
}

deque<int> q;
int sum[N],ans=0xcfcfcfcf;
int n,m;
int main()
{
	n=read(); m=read();
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+read();
	q.push_back(0);
	for(int i=1;i<=n;i++)
	{
		while(q.size()&&q.front()<i-m) q.pop_front();
		ans=max(ans,sum[i]-sum[q.front()]);
		while(q.size()&&sum[q.back()]>=sum[i]) q.pop_back();
		q.push_back(i);
	}
	printf("%d",ans);
	return 0;
}
上一篇:1107 老鼠爱大米 (20 分)


下一篇:CSS3中min-width与max-width用法