#include <iostream>
#include <stdio.h>
using  namespace std;

int main()
{
	int T;
	scanf("%d",&T);
	int** Matrix = new int*[T];
	int* array = new int[T];
	int i = 0;
	int n,j,m;
	int max1,max2,max,sum1,sum2;
	int s1,t1,s2,t2,test_case = T;
	while (test_case--)
	{
		scanf("%d",&n);
		Matrix[i] = new int[n];
		for (j = 0;j < n;++j)
		{
			scanf("%d",&Matrix[i][j]);
		}
		if (n == 2)
		{
			array[i] = Matrix[i][0] + Matrix[i][1];
		}
		else
		{
			int* max_array1 = new int[n - 1];
			
			sum1 = 0;
			max1 = Matrix[i][0];
			for (t1 = 0;t1 < n - 1;++t1)
			{		
				if (sum1 > 0)
				{
					sum1 += Matrix[i][t1];
				}
				else
				{
					sum1 = Matrix[i][t1];
				}
				if (max1 < sum1)
				{
					max1 = sum1;
				}
				max_array1[t1] = max1;
			}
			
			int* max_array = new int[n];
			sum2 = 0;
			max2 = Matrix[i][n - 1];
			for (t1 = n - 1;t1 >= 1;--t1)
			{
				if (sum2 > 0)
				{
					sum2 += Matrix[i][t1];
				}
				else
				{
					sum2 = Matrix[i][t1];
				}
				if (max2 < sum2)
				{
					max2 = sum2;
				}
				max_array[t1] = max2;
			}
			
			
			max1 = Matrix[i][0];
			max2 = max_array[1];
			max = max1 + max2;
			for (t1 = 0;t1 < n - 1;++t1)
			{
				max1 = max_array1[t1];
				max2 = max_array[t1 + 1];
				if (max < max1 + max2)
				{
					max = max1 + max2;
				}
			}
			
			array[i] = max;
			delete[]Matrix[i++];
			delete[]max_array;
		    delete[]max_array1;
		}
		++i;
	}

	for (i = 0;i < T;++i)
	{
		printf("%d\n",array[i]);
	}

	return 0;
}

• Re:老是 wa 大牛们帮忙给看看 不胜感激 (1809) fumingma2 2009-08-25 17:37:02