分治策略结合递归思想求最大子序列和

我的主力博客：半亩方塘

对于 《数据结构与算法分析——C语言描写叙述》 一书第 20 页所描写叙述的算法 3，相信会有非常多人表示不怎么理解，以下我由详细问题的求解过程出发，谈谈我自己的理解：

首先，什么是分治法呢？所谓 分治法，就是 将一个问题的求解过程分解为两个大小相等的子问题进行求解，假设分解后的子问题本身也能够分解的话，则将这个分解的过程进行下去，直至最后得到的子问题不能再分解为止，最后将子问题的解逐步合并并可能做一些少量的附加工作，得到最后整个问题的解。在求解原来整个问题的算法思想，与求解每个子问题的算法思想全然同样，则能够用到递归来解决问题，在我的博文 关于递归的一些简单想法 中，曾指出，当我们要解决的问题有着 重复运行的基本操作 的时候，能够考虑使用递归，在这里，原来的整个的问题与每个分解后子问题都有着重复运行的算法思想，这就是一个基本操作，所以能够用递归实现，关于递归，在我的博文 由递归思想处理问题的基本原则 中，给出了有关递归思想的部分描写叙述。

回到我们标题所阐述的问题，求最大子序列和，我们能够将求最大子序列和的序列分解为两个大小相等的子序列，然后在这两个大小相等的子序列中，分别求最大子序列和，假设由原序列分解的这两个子序列还能够进行分解的话，进一步分解，直到不能进行分解为止，使问题逐步简化，最后求最简化的序列的最大子序列和，沿着分解路径逐步回退，合成为最初问题的解。我们知道，最大子序列和仅仅可能在三个位置求出：

1. 序列的左半部分的最大子序列和
2. 序列的右半部分的最大子序列和
3. 横跨序列左半部分和右半部分得到的最大子序列和：对包括左半部分的最后一个元素的最大子序列和以及包括右半部分第一个元素的最大子序列和二者求和所得到的值
4. 比較三者的大小，最大者即为所求的最大子序列和

以下我们通过详细的实例来细致体会一下这样的 分治 的算法思想。

假设我们要求以下序列的最大子序列：

4 -3 5 -2 -1 2 6 -2

将这个子序列存放在一个数组中来考虑，则有 int a[8] = {4, -3, 5, -2, -1, 2, 6, -2}。

依照分治法的思想，首先将这个序列分为左右两半部分，分界点 是 序列首元素在数组中的下标和尾元素在数组中的下标的和除以 2 所得到的下标值。在上面的序列中，分界点就是 (0 + 7)/2 = 3，也就是说分界点是下标为 3 的元素，即 -2，依照这个分界点，将序列分为两半部分，左半部分子序列为：

4 -3 5 -2

右半部分子序列为：

-1 2 6 -2

我们要在分解后所形成的两个子序列中，分别求最大子序列和，我们最好还是用左半部分的子序列来分析一下：

4 -3 5 -2

求这个左半部分子序列的最大子序列和，我们还能够将这个左半部分子序列依照上面提到的方法分解为左半部分和右半部分，由上面的分解方法，得到分界点为下标是 1 的元素，即 -3，由此我们得到左半部分的子序列为：

4 -3

右半部分的子序列为：

5 -2

上面得到的左半部分子序列和右半部分子序列要分别求最大子序列和，相同，这两个子序列仍然能够分解为左半部分和右半部分，针对上面得到的左半部分的子序列，由上面的分解方法，这里省略分解过程，得到最后的左半部分子序列为：

4

右半部分子序列为：

-3

针对 5 -2 ，得到左半部分的子序列为：

5

右半部分的子序列为：

-2

针对上面分解所得到的子序列，每个子序列仅仅含有一个元素，这是子序列的最简情形，即首元素在数组中的下标和尾元素在数组中的下标同样（首元素和尾元素为同一元素），此时序列不能再进行分解了（ 这样的情况将得到递归的基准情形 ）。

考虑上面最后得到的不能分解的子序列，依照最先提到的求最大子序列和的算法思想（1.2.3.4.），能够得到例如以下结论：

显然，针对序列 4 -3，左半部分子序列的最大子序列和是 4（是左半部分子序列本身）；右半部分子序列的最大子序列和是 -3（是右半部分子序列本身）；左半部分子序列中包括最后一个元素 4 的最大子序列和为 4，右半部分子序列中包括第一个元素 -3 的最大子序列和为 -3，二者求和得到横跨左半部分和右半部分的最大子序列和是 4 + (-3) = 1；在这三者中，左半部分的最大子序列和 4 是最大的，由此得到序列 4 -3 中，最大子序列和是 4。同理，针对序列 5 -2，我们能够用相同的方法得到最大子序列和为 5。

而序列 4 -3 和序列 5 -2 又各自是序列 4 -3 5 -2 的左半部分子序列和右半部分子序列，由此我们得到了序列 4 -3 5 -2 的左半部分子序列的最大子序列和为 4；右半部分的最大子序列和为 5；左半部分子序列中，包括最后一个元素 -3 的最大子序列和是 -3 + 4 = 1，右半部分子序列中，包括第一个元素 5 的最大子序列和为 5，二者求和得到横跨左半部分和右半部分的最大子序列和为 1 + 5 = 6，三者中 6 是最大的，由此，我们得到序列 4 -3 5 -2 的最大子序列和为 6。而序列 4 -3 5 -2 恰好是原序列的左半部分子序列，按照上述求原序列左半部分最大子序列和的方法，同理我们能够非常轻松地求出原序列右半部分子序列 -1 2 6 -2 的最大子序列和为 8（最好还是在草稿纸上演示一下这个过程），经过以上分析过程，我们得到：

原序列的左半部分子序列的最大子序列和是 6；原序列的右半部分子序列的最大子序列和为 8；在原序列的左半部分子序列中，包括最后一个元素 -2 的最大子序列和是 -2 + 5 + (-3) + 4 = 4，在原序列的右半部分子序列中，包括第一个元素 -1 的最大子序列和是 -1 + 2 + 6 = 7，二者求和得到横跨左半部分与右半部分的最大子序列和是 4 + 7 = 11， 6 8 11 中最大的为 11，由此我们能够得到原序列的最大子序列和为 11。

由以上分析能够看到，求一个序列的最大子序列和，是依照分治法的思想将所给序列逐步分解，分解到不能分解为止（即递归的基准情形），然后再逐步回退，分别求各个分解的子序列的最大子序列和，最后将全部的结果合成在一起得到最后的结果，这里涉及到一个 重复进行的基本操作 ，就是 分别求各个分解的子序列的最大子序列和 。

经过对以上个例的分析，我相信能够更好地理解以下由分治法和递归思想相结合的求最大子序列和的代码了：

static int MaxSubSum(const int A[], int Left, int Right)
{
    if (Left == Right)    /* 递归的基准情形 */
        return a[Left];

    int Center;
    Center = (Left + Right) / 2;   /* 求分界点 */
    int MaxLeftSum;
    MaxLeftSum = MaxSubSum(A, Left, Center);   /* 递归，求左半部分子序列的最大子序列和 */
    int MaxRightSum;
    MaxRightSum = MaxSubSum(A, Center + 1, Right);  /* 递归，求右半部分子序列的最大子序列和 */

    /* 求横跨左半部分和右半部分的最大子序列和 */
    /* 首先是左半部分子序列中包括最后一个元素的最大子序列和 */
    int MaxLeftBorderSum = A[Center], LeftBorderSum = A[Center];
    for (int i = Center - 1; i >= Left; --i) {
        LeftBorderSum += A[i];
        if (LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }

    /* 接着是右半部分子序列中包括第一个元素的最大子序列和 */
    int MaxRightBorderSum = A[Center + 1], RightBorderSum = A[Center + 1];
    for (int i = Center + 2; i <= Right; ++i) {
        RightBorderSum += A[i];
        if (RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }

    /* Max3 返回左、右半部分子序列的最大子序列和以及横跨左、右半部分的最大子序列和中的最大者 */
    return Max3(MaxLeftSum, MaxRightSum, 
            MaxLeftBorderSum + MaxRightBorderSum);
}

int MaxSubsequenceSum(const int A[], int N)   /* 求最大子序列和 */
{
    return MaxSubSum(A, 0, N - 1);
}