记录编号	336926	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 最大和	最终得分	100
用户昵称	404	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2016-11-03 19:43:14	内存使用	2.62 MiB

#include<bits/stdc++.h>
using namespace std;
int n,cnt,ans,pos;
int a[202000];
int f[202000];
int s[202000];
void work()
{
    int res=0;
    for(int i=1;i<=2*n;i++)s[i]=s[i-1]+a[i];
    for(int i=1;i<=2*n;i++)
	    for(int j=i;j<=2*n&&j-i+1<=n;j++)
                res=max(res,s[j]-s[i-1]);
    printf("%d\n",res); 

}
int main()
{
    freopen("maxsum.in","r",stdin);
    freopen("maxsum.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];
    if(n<=300){work();return 0;}
    f[1]=a[1];cnt=1,pos=1;
    for(int i=2;i<=2*n;i++)
    { 
        if(f[i-1]<0)f[i]=a[i],cnt=1,pos=i;
	else if(cnt==n)f[i]=f[i-1]+a[i]-a[pos],pos++;
	else f[i]=f[i-1]+a[i],cnt++;
	ans=max(ans,f[i]);
    }printf("%d\n",ans);
}