最大子序列的求解-算法之一分析

要求：给定整数序列，求解其中最大子序列（连续的序列）。

利用“分治”和递归的思想求解，在 《数据结构与算法分析（Java语言描述）》 Page29，作者给出了具体的 java 代码。

总体思路是，原序列的子序列存在于三处，左、右和跨中点。将序列从中点分割，分别用递归求出左右最大的子序列；分别求出包含左侧和右侧包含中点端点的最大子序列，求和即是跨中点的最大子序列。最后三者中的最大者即为答案。这三个步骤分别表示为①、②、③。

程序中， maxSumRec 为递归函数，函数开始为是否到达递归基准的if判断语句，然后分别是两个递归语句，执行步骤①②。对于递归而言，递归语句后边的语句不再执行，从递归语句处直接返回程序开始进行递归，直到到达基准语句，执行return跳出函数。递归语句计算出 maxLeftSum 和 maxRightSum 。

函数中，递归语句后边的部分计算步骤③，在for循环中，固定中点端点，分别想左右两侧循环求和，利用if语句来更新包含中心端点的 maxLeftBorderSum 和 maxRightBorderSum 。两个 变量求和即是③的最大子序列。

最后，求出最大者即可。整个程序给人的启发是，如果按照这种思路，我可能会对步骤①②和③分别定义函数。而作者很巧妙的定义一个函数，利用递归的执行特性，将函数前后分隔开来。测试函数在调用 maxSumRec 函数时，传入的参数为（a，0，a.length-1），这样可以首先计算①②。在递归结束得到 maxLeftSum 和 maxRightSum 后，继续执行递归语句后的部分，计算步骤③。从感官上，程序更加简洁，没有多余的函数和调用。

启发之二，使用递归的时候，需要在递归语句前边，提前设置好到达基准的条件（if，return/break），以便适时完成递归，跳出递归函数。