本文主要是介绍最大子序和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#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;
}
这篇关于最大子序和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!