#include<iostream>
#include<fstream>
#include<cmath>
#define Max_Size 100000
using namespace std;

int n,a[Max_Size],bl[Max_Size],br[Max_Size],cl[Max_Size],cr[Max_Size];

int main()
{
     int N,i;
     scanf("%d",&N);
     do
     {
       scanf("%d",&n);
       for (i=0;i<n;++i) scanf("%d",&a[i]);
       bl[0]=cl[0]=a[0];
       br[n-1]=cr[n-1]=a[n-1];
       int i,Max=-2100000000;
       for (i=1;i<n;++i)
       {
         bl[i]=max(bl[i-1],0)+a[i];
         cl[i]=max(bl[i-1],bl[i]);
       }
       for (i=n-2;i>=0;--i)
       {
         br[i]=max(br[i+1],0)+a[i];
         cr[i]=max(br[i+1],br[i]);
       }
       for (i=0;i<n-1;++i) Max=max(Max,(cl[i]+cr[i+1]));
       printf("%d\n",Max);
     }while (--N);
    system ("pause");
    return 0;
}