#include <iostream>
#include <stdio.h>
using namespace std;
#define MIN -0xfffffff

int Data[50001];//元数据
int x[50001];//从前往后经过每一点的最大sum值

int main()
{
	//输入case次数
	int time = 0;
	scanf("%d", &time);
	//cin>>time;

	int num = 0;
	
	//初始化数组

	while (time--)
	{
		//输入元数据个数
		//cin>>num;
		scanf("%d", &num);
		int sum = 0;
		int temp = MIN;
		int out = MIN;

		//输入元数据并求 从前往后数，到达每一点 并包括该点 的子片段的最大和
		for (int i=1; i<=num; i++)
		{
			//cin>>Data[i];
			scanf("%d", &Data[i]);
			sum += Data[i];
			if (sum > temp)
			temp = sum;
			x[i] = temp;
			if (sum < 0)//这一步的判断使得之前超时的部分得以简化，减少了一轮for
				sum = 0;
		}
		temp = MIN;
		sum = 0;
		//从后往前数，到达每一点 并包括该点 的子片段的最大和
		for (int j=num; j>=2; j--)
		{
			sum += Data[j];
			if (sum > temp)
				temp = sum;
			if (x[j - 1] + temp > out)
			{
				out = x[j - 1] + temp;
			}
			if (sum < 0)
				sum = 0;
		}
		printf("%d\n", out);
		//cout<<out<<endl;
	}
	return 0;
}