记录编号	263827	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 最大和	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-05-26 18:13:16	内存使用	0.21 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<deque>
using namespace std;
namespace mine{
	int __c,__x,__a[110],__i,__j;
	bool __neg;
	inline int getint(){
		__x=__neg=0;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=(__x<<1)+(__x<<3)+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline void putint(int __x){
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j>=0;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
template<typename T>
struct deque{
private:
	static const int maxn=1010;
	T a[maxn];
	int head,tail;
public:
	inline deque(){
		//memset(a,0,sizeof(a));
		head=tail=0;
	}
	inline void clear(){
		deque();
	}
	inline int size(){
		return head>tail?tail-head+maxn:tail-head;
	}
	inline bool empty(){
		return head==tail;
	}
	inline void push_back(const T& n){
		a[tail++]=n;
		if(tail==maxn) tail=0;
	}
	inline T pop_front(){
		T n=a[head++];
		if(head==maxn)head=0;
		return n;
	}
	inline void push_front(const T& n){
		if(head==0)head=maxn+1;
		a[--head]=n;
	}
	inline T pop_back(){
		if(tail==0)tail=maxn+1;
		T n=a[--tail];
		return n;
	}
	inline T& front(){
		return a[head];
	}
	inline T& back(){
		if(tail==0)return a[maxn-1];
		return a[tail-1];
	}
	inline T& end(){
		if(tail==0)return a[maxn-1];
		return a[tail-1];
	}
	inline bool in(const int &n){
		for(int i=0;i<size();i++)if(a[head+i>=maxn?head+n-maxn:head+n]==n)return true;
		return false;
	}
	inline T& operator[](const int& n){
		if(head+n>=maxn)return a[head+n-maxn];
		return a[head+n];
	}
};
const int maxn=100100;
int b[maxn<<1],n,ans=-0x7ffffff;
deque<int>q;
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("maxsum.in","r",stdin);
	freopen("maxsum.out","w",stdout);
#endif
	n=getint();
	b[0]=0;
	for(int i=1;i<=n;i++){
		b[i]=getint();
		b[i+n]=b[i];
		b[i]+=b[i-1];
	}
	for(int i=n+1;i<=(n<<1);i++)b[i]+=b[i-1];
	for(int i=1;i<=(n<<1);i++){
		while(!q.empty()&&b[q.back()]>=b[i])q.pop_back();
		q.push_back(i);
		if(q.front()<=i-n)q.pop_front();
		ans=max(ans,b[i]-b[q.front()]);
	}
	putint(ans);
	return 0;
}
int haha=MAIN();
int main(){;}