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

#include<cstdio>
#include<iostream>
using namespace std;
main()
{
	freopen("maxsum.in","r",stdin);
	freopen("maxsum.out","w",stdout);
	int a[100010],b,f[2][100010],i,l[100010],m=0,n,s,t,u=0;
	cin>>n>>a[1];
	s=a[1];
	for(i=2;i<=n;i++)
	{
		cin>>a[i];
		s+=a[i];
		if(a[i]*a[i-1]>=0)
		{
			a[i-1]+=a[i];
			i--;
			n--;
		}
	}
	for(i=1;i<=n;i++)
	{
		t=f[0][i-1]+a[i];
		f[0][i]=max(t,0);
		m=max(f[0][i],m);
	}
	for(i=1;i<=n;i++)
	{
		t=f[1][i-1]+a[i];
		f[1][i]=min(t,0);
		u=min(f[1][i],u);
	}
	b=s-u;
	if(b<m)
		b=m;
	cout<<b;
}