#include<stdio.h>
int main()
{int test,n,i,j,k,sum,max,max1,max2,a[50001],j0;
 scanf("%d",&test);
 //getchar();
 while(test--)
 {scanf("%d",&n);
  for(i=1;i<=n;i++)scanf("%d",&a[i]);
  sum=max1=max2=0;j=0;
  for(i=1;i<=n;i++)
  {if(sum>max1){max1=sum;j=i-1;}
   sum+=a[i];
   if(sum<0)sum=0;
  }sum=max2=0;
  //printf("max1=%d\n",max1);
  for(i=j;i>0;i--)
  {if(a[i]<0){k=i;break;}
   max2+=a[i];
   max1-=a[i];
  }max1=sum=0;
  for(i=1;i<=k;i++)
  {if(sum>max1)max1=sum;
   sum+=a[i];
   if(sum<0)sum=0;
  }sum=0;
  for(i=j+1;i<=n;i++)
  {if(sum>max1)max1=sum;
   sum+=a[i];
   if(sum<0)sum=0;
  }
 if(max1==0)
  {max1=a[1];j=1;
   for(i=2;i<=n;i++)
   if(a[i]>max1&&a[i]!=max2){max1=a[i];j=i;}
  }//printf("j=%d\n\n",j);

  if(max2==0)
  {if(j!=1)
   {max2=a[1];
    for(i=2;i<=n;i++)
    if(a[i]>max2&&i!=j)max2=a[i];
   } 
   if(j==1) 
   {max2=a[2];//j0=2;
    for(i=3;i<=n;i++)
		if(a[i]>max2)max2=a[i];
   }  
  }

  max=max1+max2;
  //printf("max1=%d max2=%d max=%d\n",max1,max2,max);
  printf("%d\n",max);
 }
}
/*
10

10
-1 -1 -2 -2 -3 -3 -4 -4 -5 -5
10
1 -1 2 2 3 -3 4 -4 5 -5
10
1 -1 -2 -2 -3 -3 4 -4 5 -5
10
-1 -1 -2 -2 -3 -3 -4 -4 5 -5
Sample Output

13
*/

• Re:Why wrong??? (1377) loves 2007-05-22 21:44:12
• Re:Why wrong??? (7) loves 2007-05-22 21:44:35