动态规划
#include < stdio.h >

#include < stdlib.h >

#define MIN -100000

int num1[50005];
int num2[50005];

int dp1[50005];
int dp2[50005];

int cmp ( const void *a, const void *b )
{
    
    return *( int * )a - *( int * )b;
}

void find ( int n, int s[], int dp[] )
{
    
    int sum = 0;
    int ans = MIN;
    
    for ( int i=0; i<n; i++ )
    {
        if ( sum > 0 )
        {
            sum += s[i];
        }
        else
        {
            sum = s[i];
        }
        if ( sum > ans )
        {
            ans = sum;
        }
        dp[i] = ans;
    }
}

int check ( int n )
{
    
    int count = 0;
    for ( int i=0; i<n; i++ )
    {
        if ( num1[i] > 0 )
        {
            count ++;
        }
    }
    
    return count;
}

int main ()
{
    
    int t, n;
    int i;
    int max;
    int left, right;
    
    scanf ( "%d", &t );
    getchar ();
    getchar ();
    while ( t -- )
    {
        scanf ( "%d", &n );
        for ( i=0; i<n; i++ )
        {
            scanf ( "%d", &num1[i] );
            num2[n-i-1] = num1[i];
        }
        
        if ( check ( n ) < 2 )
        {
            qsort ( num1, n, sizeof ( int ), cmp );
            
            printf ( "%d\n", num1[n-2]+num1[n-1] );
        }
        else
        {
            find ( n, num1, dp1 );
            find ( n, num2, dp2 );
            
            max = MIN;
            for ( i=0; i<=2*n; i++ )
            {
                if ( i&1 )
                {
                    left = i / 2;
                    right = n - ( i / 2 + 1 ) - 1;
                }
                else
                {
                    left = i / 2 - 1;
                    right = n - ( i / 2 + 1 ) - 1;
                }
                if ( left >= 0 && left < n && right >= 0 && right < n )
                {
                    if ( dp1[left] + dp2[right] > max )
                    {
                        max = dp1[left] + dp2[right];
                    }
                }
            }
            
            printf ( "%d\n", max );
        }
        
    }
    return 0;
}