POJ2479——动态规划求最大子段

题目大意：

求一共序列的两个字段最大和。

例如

1 -1 2 2 3 -3 4 -4 5 -5
In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.
答案是 13

 

 

分析：

在做这道题之前，我们先看看求一序列的最大子段是怎样求的。

设a[i]为序列的第i个元素。设b[j]为i到j的子段和的最大值（i从0变化到j），那么当b[j-1]>0时,b[j]=b[i-1]+a[j],

否则 b[j]=a[i];那么b数组中的最大值既所求子段。那么我们可以写下如下程序

 

#include<iostream>
using namespace std;
int main()
{
	int a[100];
	int n;
	int b;
	int i;
	int sum;
	cin>>n;
	for(i=0;i<n;i++)
		cin>>a[i];
	b=a[0];
	sum=a[0];
	for(i=1;i<n;i++)
	{
		if(b>0)
			b=b+a[i];
		else
			b=a[i];
		if(sum<b)
			sum=b;
	}
	cout<<sum<<endl;
	return 0;

}

 

 

 好的，现在我们通过上面的程序已经会求一个序列的最大子段了，我们在回过来看这道题哦，它是要求两个子段的和最大，那么我们该怎么从求序列的最大子段，求两个子段的最大和呢？我们假设所求两个子序列最大和为sum,两个子序列分别为left和right，这两个子段一个在序列的左边，一个在右边。那么在它们中间必定有一个分割点（这个点即可能被包含在其中一个子段中，也可能不。）设这个点为k，那么left必定是从0到k这个子段的最大子序列（用反证法证明，假设存在在0到k这个范围内的一个子序列nleft的比left大，那么nleft+right将大于sum,这就与上面假设最和为sum矛盾，所以必定不成立比left大的nleft），right必定是从k+1到n-1(n为序列长度)这个子段的最大子序列（证明过程同上），那么我们现在的问题就转换成了求两个最大子序列。我们从左边开始，往右边求出每个点的最大左子段和，保存在b[]数组中，然后再从右边开始，往左边求出每个点的最大右子段和，然后再遍历每个点，求出每个点的两个最大左右子段和，即可得出答案。

代码如下。

#include<iostream>
using namespace std;
#define len 50010
int main()
{
	int a[len];
	int b[len];
	int c[len];
	int num;
	int i;
	int n;
	scanf("%d",&num);
	while(num--)
	{
		scanf("%d",&n);//注意这道题用cin输入会超时
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
//以下代码为从左往右，求出每个点的右边最大子段
		b[0]=a[0];
		for(i=1;i<n;i++)
		{
			if(b[i-1]>0)
				b[i]=b[i-1]+a[i];
			else
				b[i]=a[i];
		}
		for(i=1;i<n;i++)
		{
			if(b[i]<b[i-1])
				b[i]=b[i-1];
		}
//以下代码为从右往左，求出每个点的左边最大子段
		c[n-1]=a[n-1];
		for(i=n-2;i>=0;i--)
		{
			if(c[i+1]>0)
				c[i]=c[i+1]+a[i];
			else
				c[i]=a[i];
		}
		for(i=n-2;i>=0;i--)
		{
			if(c[i]<c[i+1])
				c[i]=c[i+1];
		}
//遍历每个点的子段和，求出最大的那个
		int s=b[0]+c[1];
		for(i=0;i<n-1;i++)
		{
			if(b[i]+c[i+1]>s)
				s=b[i]+c[i+1];
		}
		printf("%d\n",s);
	}
	return 0;
}