各位大牛,近来我做了一道pku的题,别人评价是简单题,但不知道为什么老是WA,诚请各位帮帮忙,谢谢!
它的原题是:
Maximum sum 
Time Limit:1000MS  Memory Limit:65536K

Description
Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below: 
                     t1     t2 
         d(A) = max{ ∑ai + ∑aj | 1 <= s1 <= t1 < s2 <= t2 <= n }
                    i=s1   j=s2
Your task is to calculate d(A). 
Input
The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input. 
Each test case contains two lines. The first line is an integer n(2<=n<=50,000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10,000).There is an empty line after each case.
Output
Print exactly one line for each test case. The line should contain the integer d(A).
Sample Input
1

10
1 -1 2 2 3 -3 4 -4 5 -5
Sample Output
13
Hint
In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer. 
Huge input,scanf is recommended.
Source
POJ Contest,Author:Mathematica@ZSU

下面是我的代码:
#include <stdio.h>

int a[50000],ll[50000],rr[50000];
void MaxSum(int left,int right)
{
    int sum=-50000,d=0,i;
    for(i=left;i<=right;i++)
    {
        if(d>0)
            d+=a[i];
        else
            d=a[i];
        if(d>=sum)
        {
            ll[i]=d;
            sum=d;
        }
        else
            ll[i]=sum;
        
    }
}

void MaxSum_r(int right,int left)
{
    int sum=-50000,d=0,i;
    for(i=right;i>=left;i--)
    {
        if(d>0)
            d+=a[i];
        else
            d=a[i];
        if(d>=sum)
        {
            sum=d;
            rr[i]=d;
        }
        else 
            rr[i]=sum;
        
    }
}

int main()
{    
    long sum=-500000000,mid;
    int t,n,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        
        MaxSum(0,n-1);
        MaxSum_r(n-1,0);
    
        for(mid=0;mid<n-1;mid++)
        {
            if(ll[mid]+rr[mid+1]>sum)
                sum=ll[mid]+rr[mid+1];
        }
        printf("%d\n",sum);

    }


    return 1;
}

在下很大程度上认为是输入有问题,因为题目要求:"There is an empty line after each case.",可我就是改不正确.
我的思路是,对输入的数组进行从左到右用动态规划思想求出:从最左边到当前位置的最大数和;再从右到左类似操作.最后再结合ll[]和rr[]求出解答.
在此再次麻烦大家了!谢谢!