最大字段和问题 难点分析和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];elsesum = 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；可以用在整数和浮点数序列中。