poj2479——Maxnum sum

做两次dp.

对于数组dp[i]，表示下标从1到i的最大连续和。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 50005
#define maxcost 9999999
int dp[maxn],num[maxn];
int main()
{
	int t,i,n,max,sum;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(i=1;i<=n;i++)
			scanf("%d",&num[i]);
		sum=0;max=-maxcost;
		for(i=1;i<n;i++)
		{
			sum+=num[i];
			if(sum>max) max=sum;
			dp[i]=max;
			if(sum<0) sum=0;
		}
		max=-maxcost;sum=0;
		int ans=-maxcost;
		for(i=n;i>1;i--)
		{
			sum+=num[i];
			if(sum>max)max=sum;
			if(max+dp[i-1]>ans) ans=max+dp[i-1];
			if(sum<0) sum=0;
		}
		cout<<ans<<endl;
	}
	return 0;
}