#include<iostream>
using namespace std;

int main()
{
	int Right[50008];
	int Lift[50008];
	int Array[50008];
	int Start;
	int End;
	int i;
	int t,n;
	int max;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for( i = 1 ; i <= n ; i++ )
		{
			scanf("%d",&Array[i]) ;
		}
		End = Array[1];
		Lift[1] = Array[1];
		for( i = 2 ; i <= n ; i++ )
		{
			if(Array[i]>Array[i]+End)
			{
				End=Array[i];
			}
			else
			{
				End=Array[i]+End;
			}
			if(End>Lift[i-1])
			{
				Lift[i]=End;
			}
			else
			{
				Lift[i]=Lift[i-1];
			}
		}
		Start = Array[n] ;
		Right[n] = Array[n];
		for( i=n-1 ; i>=1 ;i-- )
		{
		
			if(Array[i]>Start+Array[i])
			{
				Start=Array[i];
			}
			else
			{
				Start+=Array[i];
			}
		
			if(Right[i+1]>Start)
			{
				Right[i]=Right[i+1];
			}
			else
			{
				Right[i]=Start;
			}
		}
		max=INT_MIN;
		for( i = 1 ; i <= n ; i++ )
		{
		
			if(max<Right[i+1] + Lift[i])
			{
				max=Right[i+1] + Lift[i];
			}
			
		}
		printf("%d\n", max);
	}
	return 0;
}

• Re:求助~~~开始TL 后来又WA~~郁闷 (251) s2009zy 2010-06-01 13:11:09