#include<iostream>
#include<algorithm>
using namespace std;
int kadan(int a[],int n)
{
    int cs=0;
    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;
}
int main() {
 
 int t;
 cin>>t;
 while(t--)
 {
     int n;
     cin>>n;
     int sum=0;
     int a[n];
     int c[n];
     for(int i=0;i<n;i++)
     {
         cin>>a[i];
     }
    for(int i=0;i<n;i++)
    {
            c[i]=-a[i];
    }
for(int i=0;i<n;i++)
{
    sum=sum+a[i];
}
 
cout<<sum+kadan(c,n)<<endl;
 }
	return 0;
}

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGFsZ29yaXRobT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IGthZGFuKGludCBhW10saW50IG4pCnsKICAgIGludCBjcz0wOwogICAgaW50IG1zPTA7CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKXsKICAgICAgICBjcz1jcythW2ldOwogICAgICAgIGlmKGNzPDApCiAgICAgICAgewogICAgICAgICAgICBjcz0wOwogICAgICAgIAogICAgICAgIH0KICAgICAgICBtcz1tYXgoY3MsbXMpOwogICAgfQogICAgcmV0dXJuIG1zOwp9CmludCBtYWluKCkgewoKIGludCB0OwogY2luPj50Owogd2hpbGUodC0tKQogewogICAgIGludCBuOwogICAgIGNpbj4+bjsKICAgICBpbnQgc3VtPTA7CiAgICAgaW50IGFbbl07CiAgICAgaW50IGNbbl07CiAgICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgICB7CiAgICAgICAgIGNpbj4+YVtpXTsKICAgICB9CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgewogICAgICAgICAgICBjW2ldPS1hW2ldOwogICAgfQpmb3IoaW50IGk9MDtpPG47aSsrKQp7CiAgICBzdW09c3VtK2FbaV07Cn0KCmNvdXQ8PHN1bStrYWRhbihjLG4pPDxlbmRsOwogfQoJcmV0dXJuIDA7Cn0=

Mgo4CjEwICAtMyAgLTQgIDcgIDYgIDUgIC00ICAtMQo5CjExIDEwIC0yMCA1IC0zIC01IDggLTEzIDEw

2
8
10  -3  -4  7  6  5  -4  -1
9
11 10 -20 5 -3 -5 8 -13 10