/*  看数据没想到是(O)n的算法，求出从前向后的最大子段和和从后向前的最大子段和，  然后枚举断点。   第一次提交不小心折在数组最小值的赋值上…… */ #include<cstdio>#include<iostream>#include<cstring>#define M 50010#define INF 1000000000using namespace std;int a[M],f1[M],f2[M],v1[M],v2[M],n;int main(){    int T;scanf("%d",&T);    while(T--)    {        memset(f1,466,sizeof(f1));        memset(f2,466,sizeof(f2));        memset(v1,466,sizeof(v1));        memset(v2,466,sizeof(v2));        scanf("%d",&n);        for(int i=1;i<=n;i++)          scanf("%d",&a[i]);        for(int i=1;i<=n;i++)          f1[i]=max(f1[i-1]+a[i],a[i]),v1[i]=max(f1[i],v1[i-1]);        for(int i=n;i>=1;i--)          f2[i]=max(f2[i+1]+a[i],a[i]),v2[i]=max(f2[i],v2[i+1]);        int ans=-INF;        for(int i=1;i<n;i++)          ans=max(ans,v1[i]+v2[i+1]);        printf("%d\n",ans);    }    return 0;}