最大子序和

本文主要是介绍最大子序和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#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;
}

这篇关于最大子序和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！