POJ 2479 最大数字连续和 动态规划

在输入的同时，进行一次DP，计算出从左到右的最大值，并把它保存在数组dp的对应的下标元素中，这样之后，对于下标为i的元素，它其中保存的便是前面所有元素可能的最大连续和。再从右到左进行一次DP，计算从右到左的最大连续和。假设此时已经算到下标为i的元素，那么将sum+dp[i-1]与ans进 行比较，将ans取较大者。最后当i到2的时候ans中的值即为所求的最大值。

#include <iostream>
using namespace std;
int dp[100001],num[100001];
const int MINNUM = -99999999;
int main(){
	int cases,n,temp,i,sum,ans;
	cin>> cases;
	while(cases--){
		scanf("%d",&n);
		temp = MINNUM;
		sum = 0;
		for (i = 1;i <= n;i++)
		{
			scanf("%d",&num[i]);
			//先从左向右求最大子段和
			sum += num[i];
			if(sum > temp)
				temp = sum;
			dp[i] = temp;
			if (sum < 0)
				sum = 0;
		}
			
			//在从右向左找右边的字段和与左边字段和最大值
			temp = ans = MINNUM;
			sum = 0;
			for (i = n;i > 1;i--)
			{
				sum += num[i];
				if (sum > temp)
					temp = sum;
				if (ans < dp[i-1] + temp)
					ans = dp[i-1] + temp;
				if (sum < 0)
					sum = 0;
			}	
			cout<<ans<<endl;
	}
	return 0;
}