#include <stdio.h>
#include <string.h>
int a[50010]={0},b[50010]={0},c[50010]={0};
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {        
        int i,j,max,sum,n;
        printf("\n");
        scanf("%d",&n);
        n--;
        for(i=0;i<=n;i++)
        scanf("%d",&a[i]);
        b[0]=0;
        c[0]=0;
        for(i=1;i<=2;i++)
        {
            b[i]=b[i-1]+a[i];
            c[i-1]=b[i];
            max=b[i];
            for(j=i+1;j<=i+n-2;j++)
            {
                b[j]=b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];
                c[j-1]=max;
                if(max<b[j])max=b[j];
            }
            c[i+n-2]=max;
        }
        sum=0;
        for(j=2;j<=n;j++)
        if(sum<b[j])sum=b[j];
        printf("%d\n",sum);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));        
    }
    return 0;
}
    

• Re:没有考虑全是负数的情况 (83) bjss222 2007-04-06 21:00:42