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;
}