infinity

http://acm.pku.edu.cn/JudgeOnline/problem?id=2593
最大m子段問(wèn)題，此題中m=2。方法還是DP，基本上還是用我們熟悉的最大子段和的方法。
讀入數(shù)據(jù)是時(shí)做一次DP，得到從前往后到第i（0=<i<n）個(gè)元素處時(shí)的最大子段和，然后再
從后往前反向做一次DP，加上前面求得的正向的最大字段和即可求出一個(gè)最大值。

Memory: 988K		Time: 172MS
Language: C		Result: Accepted

#include<stdio.h>
int main()
{
    int n,num[100000],MaxSum[100000];
    while(scanf("%d",&n),n){
        int i,sum=0,max=-100000,ret=-0x7fffffff;
        for(i=0;i<n;i++) {
            scanf("%d",&num[i]);
            if(sum>0) sum+=num[i];else sum=num[i];
            if(sum>max) max=sum;
            MaxSum[i]=max;
        }
        for(max=-0x7fffffff,sum=0,i=n-1;i>=1;i--){
            if(sum>0) sum+=num[i];else sum=num[i];
            if(sum>max) max=sum;
            if(max+MaxSum[i-1]>ret) ret=max+MaxSum[i-1];
        }
        printf("%d\n",ret);
    }
    return 0;
}