最大字段和问题 难点分析和C++实现9

给定n个数组成的序列，求其中最大子段和，并规定其中如果所有数均为负值的时候，那么最大字段和为零。

解决这样的问题需要用的算法是：分治法

基本思路：

1. 划分两个长度基本相同的子段，得出以下三种情况

2.如果最大和出现在左边，就左边最大子段和为解

3. 如果最大和出现在右边，就右边最大子段和为解

4. 如果是最大和在左子段的最右边的数组成，和右子段的最左边的数组成，那么就合并这两个子段和，得到最终的解

解决这个问题的关键：

1. 递归法，要熟悉递归机制，那么就比较好理解了

2. 如何把三种情况都很好的计算出来并且合并起来。这也是分治法思想的精要。

下面给出详细注释的程序：

#include<iostream>
#include<vector>

using namespace std;

template<typename T>
T sectionMaxSum(vector<T>& vt, int lIndex, int rIndex)//Index range [1,n] <=> C++Index range [0, n-1]
{
	T sum  = T(0);

	//情况0：如果只有一个元素； 也就是递归的结束条件，这也是递归算法的必要条件
	//这个算法的话必然会分治到这个情况，然后再逐层退出返回递归求的结果
	if(lIndex == rIndex)
	{
		if(vt[lIndex-1]>0)	sum = vt[lIndex-1];
		else				sum = 0;
	}
	else
	{
		//分治，划分两个相同长度的两个子序列
		int midIndex = (lIndex+rIndex)/2;

		//情况1：最大子段和为左边序列的最大子段，递归求解，注意下标设计
		T lSum = sectionMaxSum(vt, lIndex, midIndex);

		//情况2：最大子段和为右边序列的最大子段，递归求解，
		//注意：midIndex不加1的话，就会出现递归栈溢出
		T rSum = sectionMaxSum(vt, midIndex+1, rIndex);

		//情况3：最大子段为两个左右子段的最大子段的和
		T lSubMaxSum = T(0);
		T lTempSum = T(0);
		for(int i = midIndex-1; i>=lIndex-1; i--)//注意：这里lIndex-1，如果是lIndex没有-1的话，
		{								//会发生掉值，结果就会不正确.
			lTempSum += vt[i];
			if(lTempSum>lSubMaxSum) lSubMaxSum = lTempSum;
		}
		T rSubMaxSum = T(0);
		T rTempSum = T(0);
		for(int i = midIndex; i<rIndex; i++)
		{
			rTempSum += vt[i];
			if(rTempSum>rSubMaxSum) rSubMaxSum = rTempSum;
		}

		//情况1,2,3中最大者为问题最终解
		sum = lSubMaxSum + rSubMaxSum;
		if(sum<lSum)	sum = lSum;
		if(sum<rSum)	sum = rSum;
	}
	return sum;
}

void test()
{
	//初始化数组
	double a[18] = 
	{32., 12., 0.7, 5., 0.1, 0.7, 0.8,0.7, -99., 0.4, 1., 2.5, 3.6, 5., -9., 12., 19.,23.};
	vector<double> vd(a, a+18);

	//元序列输出
	for(int j=0; j<18; j++)
	{
		cout<<vd[j]<<" ";
	}
	cout<<endl;

	//调用函数
	double  sum = sectionMaxSum(vd, 1, vd.size());
	
	//最大子段和输出
	cout<<sum<<endl;
}

int main()
{
	test();
	return 0;
}

总结：

最终答案是57.7；可以用在整数和浮点数序列中。