> #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)     //dp向后扫描
> 			{		
> 				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)  //dp向前扫描
> 			{
> 				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;
> }
> 
> 
> 
>