// 最大子数组和
// Time Limit: 1000 MS      Memory Limit: 5000 KB
// Description

// 给定一个长度为N的int型数组a[0,1,2,...N-1], 请计算最大子数组和.

// Input

// 第一行输入M表示包含M组测试数据，每组先输入N (N<=50000), 接着输入N个int型整数.

// Output

// 输出最大子数组和.

// Sample Input

// 2
// 5 -1 -5 -2 -1 -3
// 5 2 -1 3 -2 4

// Sample Output

// -1
// 6
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
int main()
{
    int M;cin>>M;
    while(M--){
        int n;cin>>n;
        vector<int> a(n+1,0);
        vector<int> f(n+1,0);//f[i] means that end in i,and max sub
        for(int i=1;i<=n;i++) cin>>a[i];

        for(int i=1;i<=n;i++){
            f[i]=max(a[i],f[i-1]+a[i]);
        }
        int res=-1e9;
        for(int i=1;i<=n;i++){
            if(f[i]>res) res=f[i];
        }
        cout << res<<endl;
    }

}