记录编号	141746	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 最大和	最终得分	100
用户昵称	TA	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2014-12-03 21:15:42	内存使用	11.00 MiB

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<algorithm>
char * ptr=(char *)malloc(10000000);
int a[100001],max1[100001],max2[100002];
inline void in(int &x){
	bool flag=0;
	while(*ptr<'0'||*ptr>'9')
		if(*++ptr=='-')
			flag=1;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
	if(flag)x=-x;
}
int main(){
	freopen("maxsum.in","r",stdin);
	freopen("maxsum.out","w",stdout);
	int N,f=0,i,ans=-0x7fffffff,s;
	fread(ptr,1,10000000,stdin);
	in(N);
	for(i=1;i<=N;++i)in(a[i]);
	for(i=1;i<=N;++i){
		if(f>0)f+=a[i];
		else f=a[i];
		if(f>ans)ans=f;
	}
	max1[0]=-0x7fffffff,max2[N+1]=-0x7fffffff;
	for(s=0,i=1;i<=N;++i)s+=a[i],max1[i]=max(max1[i-1],s);
	for(s=0,i=N;i;--i)s+=a[i],max2[i]=max(max2[i+1],s);
	for(i=N;i;--i)ans=max(ans,max2[i+1]+max1[i]);
	printf("%d",ans);
}