#include <stdio.h>
#include <string.h>
int s[2][50000],p[50000];

int main()
{
	int n,m,i,max[2];
	scanf("%d",&n);
	while( n --)
	{
		scanf("%d",&m);
		for( i =0; i <m; i ++)
			scanf("%d",&p[i]);
		memset(s,0,2*m*sizeof(int));
		s[0][0] = p[0]>0?p[0]:0;
		s[1][m-1] = p[m-1]>0?p[m-1]:0;
		for( i =1; i <m; i ++)  //第一次处理
		{
			s[0][i] = s[0][i-1]+p[i];
			if( s[0][i] <0)	s[0][i] = 0;
			s[1][m-i-1] = s[1][m-i]+p[m-i-1];
			if( s[1][m-i-1] <0)	s[1][m-i-1] = 0;
		//	printf("%4d%4d\n",s[0][i],s[1][m-i-1]);
		}
		max[0] = max[1] = 0;
		for( i =0; i <m; i ++) //第二次处理
		{
			if( max[0]<s[0][i])
				max[0] = s[0][i];
			else s[0][i] = max[0];
			if( max[1]<s[1][m-i-1])
				max[1] = s[1][m-i-1];
			else s[1][m-i-1] = max[1];
		//	printf("%4d%4d\n",s[0][i],s[1][m-i-1]);
		}
		max[0] = 0;
		for( i =0; i < m-1; i ++)  //求最大
			if( max[0] <s[0][i]+s[1][i+1])
				max[0] =s[0][i]+s[1][i+1];
		printf("%d\n",max[0]);
	}
}