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

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

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

基本思路：

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

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

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

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

解决这个问题的关键：

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

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

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

#include  
#include  
  
using namespace std;  
  
template  
T sectionMaxSum(vector& 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; irSubMaxSum) rSubMaxSum = rTempSum;  
        }  
  
        //情况1,2,3中最大者为问题最终解  
        sum = lSubMaxSum + rSubMaxSum;  
        if(sum vd(a, a+18);  
  
    //元序列输出  
    for(int j=0; j<18; j++)  
    {  
        cout<

总结：

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

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