记录编号	205148	评测结果	AAAAAAAAAA
题目名称	[POJ2479+2593][NOIP2015初赛]双子序列最大和	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2015-11-04 21:05:20	内存使用	1.44 MiB

#include<cstdio>
#define Max(a,b) ((a)>(b)?(a):(b))
#define maxn 100005
using namespace std;
int n,l[maxn],r[maxn],a[maxn],Ans,p;
inline int in(){
	char c=getchar();
	int x=0;
	bool flag=0;
	if(c=='-') flag=1;
	while(c<'0'||c>'9') {
		if(c=='-') flag=1;
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
	if(flag) return -x;
	return x;
}
int B,sum;
int main(){
    freopen("Pengshuangcang.in","r",stdin);
	freopen("Pengshuangcang.out","w",stdout);
	n=in();
	for(int i=1;i<=n;++i) a[i]=in();
	sum=0;
	for(int i=1;i<=n;++i){
		B+=a[i];
		l[i]=sum;
		if(B<0){
			l[i]=0;B=0;
		}
		if(B>sum) {
			sum=B;l[i]=B;
		}
    }
	for(int i=2;i<=n;++i) l[i]=Max(l[i],l[i-1]);
	sum=B=0;
	for(int i=n;i>=1;--i){
		B+=a[i];
		r[i]=sum;
		if(B<0){
			 r[i]=B=0;
		}
		if(B>sum){
			sum=B;r[i]=B;
		}
	}
	for(int i=n-1;i>=1;--i) r[i]=Max(r[i+1],r[i]);
	Ans=l[1]+r[3];
	for(int i=2;i<n;++i) Ans=Max(Ans,l[i-1]+r[i+1]);
	printf("%d",Ans);
	return 0;
}