题意如标题
分析：
给定某一数组s1,s2,s3,...,sn,求一连续si,s(i+1),s(i+2),...,sj使其和最大.
这个问题有一个简单的DP思路,先把状态转移方程写出:sum[n]=max{sum[n-1],0}+s[n].此状态方程用语言描述:
在求sum[n]时,若前n-1个数中所求得的连续和最大值都小于0时,则把前n-1个数抛弃,从第n个数重新算后面的sum[].
实现时可以不用数组存sum,而只用一个s初始值为0,把s1,s2,...,sn一个一个顺序地加,当s<0时s=0,当s>max时,max=s;
最后求得的max即为此问题所求,复杂度为o(n).
对于poj2479来说,问题要麻烦一点,但只要弄明白了上面这个问题,这个题并不难,把数组分成s[1...i]和s[i+1...n]两部
分,枚取i,分别求出两部分的最大和,然后相加后取最大值即为问题所求.
故只需要 从左往右扫一遍求最大连续字段和，然后再从右向左扫一遍求最大连续字段和。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define INF 0xffffff
using namespace std;
int a[50010],dp[50010];
int main()
{
int T,n,sum,ans,tmp;
scanf("%d",&T);
while(T--)
{
memset(dp,0,sizeof(dp));
memset(a,0,sizeof(a));
scanf("%d",&n);
sum=0;
tmp=-INF;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
if(sum>tmp)
tmp=sum;
dp[i]=tmp;
if(sum<0) sum=0;
}
sum=0;
tmp=-INF,ans=-INF;
for(int i=n;i>=2;i--)
{
sum+=a[i];
if(tmp<sum)
tmp=sum;
if(tmp+dp[i-1]>ans)
ans=tmp+dp[i-1];
if(sum<=0) sum=0;
}
printf("%d\n",ans);
}
return 0;
}