最大子段和问题

长平狐 发布于 2013/12/25 17:25
阅读 156
收藏 1

问题描述:给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大.或者求出最大的这个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4].

求子区间及其最大值,是非常适合采用分治法德算法设计思想来设计的,其分治的思想是把一个难以直接解决的大问题,分成一些规模较小的相同性质的问题,以便各个击破,分而治之。如果规模为N的问题可以分解成k个子问题(1<k<=N),并且这些子问题之间相互独立,互不影响,递归地解决这些问题,然后合并这些子问题的解,得到最后问题的解。

分治法的代码实现过程如下:

int MaxSubSum(int a[],int left,int right)
{
	int sum = 0;		//用来存储最大子段和
	if (left == right)	//只有一个元素
	{
		sum = a[left] > 0 ? a[left] : 0;
	}
	else
	{
		int center = (left + right)/2;
		int leftsum = MaxSubSum(a,left,center);
		int rightsum = MaxSubSum(a,center+1,right);

		//下面是第三种情况
		int s1 = 0,lefts = 0;
		for (int i = center; i >= left; i --)
		{
			lefts += a[i];
			if (lefts > s1)
				s1 = lefts;
		}

		int s2 = 0,rights = 0;
		for (i = center+1; i <= right; i ++)
		{
			rights += a[i];
			if (rights > s2)
				s2 = rights;
		}

		sum = s1 + s2;
		if (sum < leftsum)
			sum = leftsum;
		if (sum < rightsum)
			sum = rightsum;
	}
	return sum;
}






原文链接:http://blog.csdn.net/zhouxuguang236/article/details/7539837
加载中
返回顶部
顶部