记录编号	44835	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 最大和	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.089 s
提交时间	2012-10-20 14:49:52	内存使用	4.67 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int a[100010],f[2][100010],last[100010];

int main(void)
{
    freopen("maxsum.in","r",stdin);
    freopen("maxsum.out","w",stdout);
    int i,n,sum,maxnum=0,minnum=0,ans,temp;
    scanf("%d",&n);
    scanf("%d",&a[1]);
	sum=a[1];
    for (i=2;i<=n;i++)
    {
        scanf("%d",&a[i]);
		sum+=a[i];
        if (a[i]*a[i-1]>=0)
        {
            a[i-1]+=a[i];
            i--;
            n--;
        }
    }
	for (i=1;i<=n;i++)
	{
		temp=f[0][i-1]+a[i];
		if (temp>0)
			f[0][i]=temp;
		else
			f[0][i]=0;
		if (maxnum<f[0][i])
			maxnum=f[0][i];
	}
	for (i=1;i<=n;i++)
	{
		temp=f[1][i-1]+a[i];
		if (temp<0)
			f[1][i]=temp;
		else
			f[1][i]=0;
		if (minnum>f[1][i])
			minnum=f[1][i];
	}
	ans=sum-minnum;
	if (ans<maxnum)
		ans=maxnum;
	printf("%d\n",ans);
    return(0);
}