#include
using namespace std;
long long int maxsum(long long int a[],long long int n);
long long int kadane(long long int a[],long long int n);
int main()
{
long long int n,a[1000000],m,t;
cin>>t;
while(t–)
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
m=maxsum(a,n);
cout<<m;
}
}
long long int kadane(long long int a[],long long int n)
{ long long int cs=0;
long long int ms=0;
for(int i=0;i<n;i++)
{
cs=cs+a[i];
if(cs<0)
{ cs=0;
}
ms=max(cs,ms);
}
return ms;
}
long long int maxsum(long long int a[],long long int n)
{ long long int totsum=0;
long long int maxarr=kadane(a,n);
for(int i=0;i<n;i++){
totsum=totsum+a[i];
}
for(int i=0;i<n;i++){
a[i]=-a[i];
}
long long int maxarr1=kadane(a,n);
long long int maxarr2=totsum+maxarr1;
return(max(maxarr,maxarr2));
}