#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50010;
const int inf=0x3f3f3f3f;
int lt[maxn],rt[maxn];//lt[i]表示从左端开始，以i结尾的子段和最大值 
int a[maxn];

void print(int a[],int n)
{
	for(int i=1;i<=n;i++)
		printf("%d  ",a[i]);
	printf("\n");
}

int main()
{
	int t,n;
	scanf("%d",&t);//1
	while(t--)
	{
		scanf("%d",&n);//8
		for(int i=1;i<=n;i++)//-5 1 2 3 -4 -8 5 12
			scanf("%d",&a[i]);
		lt[1]=a[1];
		for(int i=2;i<=n;i++)//从左向右 
			lt[i]=max(a[i],lt[i-1]+a[i]);
		printf("lt[]:\n");
		print(lt,n);
		rt[n]=a[n];
		for(int i=n-1;i>=1;i--)//从右向左
			rt[i]=max(a[i],rt[i+1]+a[i]);
		printf("rt[]:\n");
		print(rt,n);
		for(int i=n-1;i>=1;i--)//更新为从右端开始n..i个元素之中最大连续子段和 
			rt[i]=max(rt[i+1],rt[i]);
		printf("更新后的rt[]:\n");
		print(rt,n);
		int ans=-inf;
		for(int i=2;i<=n;i++)
			ans=max(ans,lt[i-1]+rt[i]);
		printf("%d\n",ans);
	}
	return 0;
}