#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN = ;

const int INF = 0x3ffffff;

int a[MAXN + ];

int left[MAXN + ],right[MAXN + ];

int main()

{

    int count;

    scanf("%d",&count);

    while(count--)

    {

        int n;

        scanf("%d",&n);

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

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

        left[] = a[];//此时left[i]表示包含i在内左边的最大子段和

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

        {

            if(left[i-]<)

                left[i] = a[i];

            else

                left[i] = a[i] + left[i-];

        }

        for(int i = ;i<n;i++)//此时left[i]表示i左边的最大子段和

            left[i] = max(left[i],left[i-]);

        right[n-] = a[n-];//此时right[i]表示包含i在内右边的最大子段和

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

        {

            if(right[i+]<)

                right[i] = a[i];

            else

                right[i] = a[i] + right[i+];

        }

        for(int i = n-;i>=;i--)//此时right[i]表示i右边的最大子段和

            right[i] = max(right[i],right[i+]);

        int num = -INF;

        for(int i = ;i<n;i++)//求每一个i左边和右边的最大子段和相加，取最大值。

            num = max(num,left[i-]+right[i]);

        printf("%d",num);

    }

    return ;

}