30. 最大连续子序列和（二）

在上一篇博文中，我们了解了最大连续子序列和的概念，也实现了两种低效算法，但是我们发现还有更加高效的算法。（好吧，其实并不是我们发现的，几乎每一本教科书里，讲到最大连续子序列和问题时，都会依次分析这4种算法，从而展现对同一问题使用不同方法，产生的效果也会不同）。

一. 最大连续子序列和-分治算法

分治算法，显然分为两大步骤：先层层切分，再层层合并。关于分治的详细内容，在这里我不展开讨论，重点关注怎么应用到本问题上。

1.实例分析

给定一组数据，data = (1, 4, -3, 7, -6, 10 )。每次切分，都从中间切。这就引出了第一个疑问点：怎么才能切到正中间？答：需要分情况讨论。当元素个数为偶数时，能够从中间切开，此时左右两边元素数量相等。当元素个数为奇数时，并不能均匀的切开，左半边总会多出一个元素。计算中间元素下标的方法是 mid = (low + high) / 2。这里的 low 就是序列开始的地方，high 就是序列结束的地方。

（1）切第一次，序列为（1, 4, -3），（7, -6, 10）。

（2）切第二次，序列为（1, 4），（-3），（7, -6），（10）。结合我上面说的奇偶情况，就可以解释为什么有的序列元素多，有的序列元素少。

（3）切第三次，序列为（1），（4），（-3），（7），（-6），（10）。现在每一个序列只有一个元素，说明切分这个动作，已经做到位了。下一步开始合并。

那么在这个问题中，应该怎么合并？合并的依据又是什么？我们需要计算子序列的和，现在每一个子序列只有一个元素，那么它的和就是这个元素本身。在“切第三次”时，我们看到，序列（1）和序列（4），它们的和分别为 1 和 4 ，那么它们合并之后的和，将会是 5 。由此我们得出结论，一个序列的最大和，可能出现在左半边，也可能出现在右半边，也可能出现在整体，此时这个拥有最大和的子序列，连接了左右两边，充当了一个桥梁的角色（因为是连续的序列，所以中间一定是要连续的）。这就引出了第二个疑问点：假如左半边最大和是第一个元素，右半边最大和是最后一个元素，那么两个最大和加起来行不行？答：当然不行。首元素和尾元素虽然都是最大和，但是它们中间隔着很多其他元素，如果中间元素都起到“负作用”，以至于加起来之后，比原有的最大和之一还要小，那么自然，总结果不能算是最大的。分析清楚了这些地方，我们就来看看代码。

2. 代码实现

int max_sub_sum_dc(const vector<int>& data, int low, int high) {
    const int MIN = numeric_limits<int>::min();

    if (low == high) {
        return data[low];
    }
    int mid = (low + high) / 2;
    int left_sum = MIN, right_sum = MIN, sum = 0;
    for (int i = mid; i >= low; --i) {
        sum += data[i];
        left_sum = max(left_sum, sum);
    }

    sum = 0;
    for (int j = mid + 1; j <= high; ++j) {
        sum += data[j];
        right_sum = max(right_sum, sum);
    }

    int half_sum = max(max_sub_sum_dc(data, low, mid), max_sub_sum_dc(data, mid + 1, high));

    return max(left_sum + right_sum, half_sum);
}

 分析这段代码，我们可以看出，第 4-6 行判断序列元素个数，如果只有一个元素，那么直接返回这个元素就行了。第 7 行将序列切分，计算左右下标。第 9-12 行计算左半边最大和，第 15-18 行计算右半边最大和。第 20 行的 half_sum 是指一半序列的最大和，也就是从左半边或右半边挑一个出来。第 22 行将挑选出的半边最大和与整体最大和作比较，留下最大的。很多同学不清楚第 20 行的递归调用，其实从前开始看，就会发现我们只计算了左半边和右半边两个子序列的和，这仅仅是两个子序列，离所有的子序列还差很远，这一点一定要明白。这一步递归，两个参数一直向下计算，直到剩余一个元素，就可以返回了。