poj2593 Max Sequence

同样是DP动态规划的题目，解题思路和poj2479也是一样的。从左到右计算并保存每个节点（包含该节点）以前所有子范围中和的最大值，再从右向左计算每个节点（包含该节点）的子范围中和的最大值，并同时计算与前半部分和，更新此最大值，直到最后输出。代码如下：

#include <cstdio>

#define SIZE 100100
#define max(a,b) a>b?a:b

int n,left,right;
int a[SIZE],max_n[SIZE],max_num,result;

int main()
{
	int i;
	scanf("%d",&n);
	while(n)
	{
		left = 0;right = 0;
		for(i=1;i<=n;i++)
		scanf("%d",a+i);
		for(i=1,max_num=-1<<31;i<n;i++)
		{
			left>0? left+=a[i]:left=a[i];
			max_num = max(max_num,left);
			max_n[i] = max_num;
		}
		for(i=n,max_num=-1<<31,result=-1<<31;i>1;i--)
		{
			right>0? right+=a[i]:right=a[i];
			max_num = max(max_num,right);
			result = max(result,max_num+max_n[i-1]);
		}
		printf("%dn",result);
		scanf("%d",&n);
	}
	return 0;
}

最后

以上就是殷勤水蜜桃为你收集整理的poj2593 Max Sequence的全部内容，希望文章能够帮你解决poj2593 Max Sequence所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。