#include<cstdio>

#include<cstdlib>

#include<cstring>

const int N=50010,INF=10010;

int a[N],f[N],mxq[N],mxh[N];

int mmax(int x,int y) {return x>y?x:y;}

int main()

{

    int T,n;

    scanf("%d",&T);

    while (T--)

    {

      scanf("%d",&n);

      for (int i=1;i<=n;i++)

        scanf("%d",&a[i]);

      int ans=-INF;

      mxq[0]=-INF,f[0]=0;

      for (int i=1;i<=n;i++)

      {

        f[i]=f[i-1]+a[i];

        mxq[i]=mmax(mxq[i-1],f[i]);

        if (f[i]<0) f[i]=0;

        /*//相同的意思

        if (f[i-1]<0) f[i]=a[i];

        else f[i]=f[i-1]+a[i];

        mxq[i]=mmax(mxq[i-1],f[i]);

        */

      }

      mxh[n+1]=-INF,f[n+1]=0;

      for (int i=n;i>=1;i--)

      {

        f[i]=f[i+1]+a[i];

        mxh[i]=mmax(mxh[i+1],f[i]);

        if (f[i]<0) f[i]=0;

      }

      for (int i=1;i<n;i++)

        ans=mmax(ans,mxq[i]+mxh[i+1]);

      printf("%d\n",ans);

    }

    return 0;

}