2018-07-27-POJ2479

题目：POJ-2479
代码：

#include<stdio.h>

#define N 50000

int main()
{
    int t,n,i,re,a[N],be[N],en[N];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",a+i);
        for(i=1,be[0]=a[0];i<n;i++)
            be[i]=be[i-1]<0?a[i]:be[i-1]+a[i];
        for(i=n-2,en[n-1]=a[n-1];i>=0;i--)
            en[i]=en[i+1]<0?a[i]:en[i+1]+a[i];
        for(i=1,re=0;i<n;i++)
        {
            if(be[i]>be[re])
                re=i;
            else
                be[i]=be[re];
        }
        for(i=n-2,re=n-1;i>=0;i--)
        {
            if(en[i]>en[re])
                re=i;
            else
                en[i]=en[re];
        }
        for(i=1;i<n;i++)
            be[i-1]+=en[i];
//以下这行原本忘记n--了，以为不会有事，没想到WA了
//be[n-1]是以a[n-1]为结尾的最大连续和，其余表示以i为
//分界线的最值.
//特例：除了最后一个元素，其余元素均为负值
        for(i=1,re=0,n--;i<n;i++)
            re=be[re]>be[i]?re:i;
        printf("%d\n",be[re]);
    }
    return 0;
}