记录编号	459900	评测结果	AAAAAAAAAA
题目名称	1190.[福州培训2010] 最大和	最终得分	100
用户昵称	699	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2017-10-16 09:25:58	内存使用	1.83 MiB

//环线上的最大和
//699

#include <cstdio>
#include <deque>

using namespace std;

const int nmax=200010;

int N;
int ans;
int res[nmax]={0};
int pre[nmax]={0};

class poi{
public:
	int val,pos;
};

deque<poi> d;

void PreDo(){
	ans=0;
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%d",&res[i]);
		res[i+N]=res[i];
	}
	for(int i=1;i<=N+N;i++){
		pre[i]=pre[i-1]+res[i];
	}
	/*
	for(int i=1;i<=N+N;i++){
		printf("%d %d\n",i,pre[i]);
	}
	printf("\n");
	*/
}

void Cal(){
	d.push_back((poi){pre[0],0});
	for(int i=1;i<=N+N;i++){
		poi bb=d.back();
		poi ff=d.front();
		while(!d.empty()&&bb.val>pre[i-1]){
			d.pop_back();
			if(!d.empty()){
				bb=d.back();
			}
		}
		while(!d.empty()&&ff.pos<i-N){
			d.pop_front();
			if(!d.empty()){
				ff=d.front();
			}
		}
		d.push_back((poi){pre[i-1],i-1});
		ff=d.front();
//		printf("ff:%d %d\n",ff.val,ff.pos);
		ans=max(ans,pre[i]-ff.val);
	}
	printf("%d\n",ans);
}

int main(){
	freopen("maxsum.in","r",stdin);
	freopen("maxsum.out","w",stdout);
	PreDo();
	Cal();
	return 0;
}