学步园

http://poj.org/problem?id=2593

http://www.cnblogs.com/devil-91/archive/2012/08/06/2625765.html

#include<stdio.h>
#include <memory.h>
#include<iostream>
using namespace std;
void run()
{
	int left[100005];
	int right[100005];
	int a[100005];
	while(1)
	{
		int n,i;
		scanf("%d",&n);
		if(n==0)break;
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		int sumL=0;
		int max=-999999;
		for(i=0;i<n;i++)
		{
			sumL=sumL+a[i];
			if(sumL>max)//注意 if(sumL>max)和if(sumL<0)不能交换
				max=sumL;
			if(sumL<0)
				sumL=0;
			left[i]=max;
		}
		max=-999999;
		int tmp=-999999;
		int sumR=0;
		for(i=n-1;i>=1;i--)
		{
			sumR=sumR+a[i];
			if(sumR>max)
				max=sumR;
			if(sumR<0)
				sumR=0;
			if(tmp<max+left[i-1])
				tmp=max+left[i-1];
		}
		printf("%d\n",tmp);
	}
}
int main()
{
	run();
	return 0;
}