绝妙的算法——最大子序列和问题

问题的引入

    给定（可能有负数）整数序列A1, A2, A3..., An， 求这个序列中子序列和的最大值。（为方便起见，如果所有整数均为负数，则最大子序列和为0）。例如：输入整数序列： -2, 11, 8, -4, -1, 16, 5, 0，则输出答案为35，即从A2～A6。

    这个问题之所以有吸引力，主要是因为存在求解它的很多算法，而这些算法的性能差异又很大。这些算法，对于少量的输入差别都不大，几个算法都能在瞬间完成，这时若花费大量的努力去设计聪明的算法恐怕就不太值得了；但是如果对于大量的输入，想要更快的获取处理结果，那么设计精良的算法显得很有必要。

切入正题

    下面先提供一个设计最不耗时间的算法，此算法很容易设计，也很容易理解，但对于大量的输入而言，效率太低：

    算法一：

    上述设计很容易理解，它只是穷举各种可能的结果，最后得出最大的子序列和。毫无疑问，这个算法能够正确的得出和，但是如果还要得出是哪个子序列，那么这个算法还需要添加一些额外的代码。

    现在来分析以下这个算法的时间复杂度。运行时间的多少，完全取决于第6、7行，它们由一个含有三重嵌套for循环中的O(1)语句组成：第3行上的循环大小为N，第4行循环大小为N-i，它可能很小，但也可能是N。我们在判断时间复杂度的时候必须取最坏的情况。第6行循环大小为j-i+1，我们也要假设它的大小为N。因此总数为O(1*N*N*N)=O(N3)。第2行的总开销为O(1)，第8、9行的总开销为O(N2)，因为它们只是两层循环内部的简单表达式。

    我们可以通过拆除一个for循环来避免3次的运行时间。不过这不总是可能的，在这种情况下，算法中出现大量不必要的计算。纠正这种低效率的改进算法可以通过观察Sum(Ai~Aj) = Aj + Sum(Ai~A[j-1])而看出，因此算法1中第6、7行上的计算过分的耗费了。下面是在算法一的基础上改进的一种算法：

    算法二：

    对于此算法，时间复杂度显然是O(N2)，对它的分析甚至比前面的分析还要简单，就是直接使用穷举法把序列中i后面的每个值相加，如果发现有比maxSum大的，则更新maxSum的值。

    对于这个问题，有一个递归和相对复杂的O(NlogN)解法，我们现在就来描述它。要是真的没有出现O(N)（线性的）解法，这个算法就会是体现递归为例的极好的范例了。该方法采用一种“分治”策略。其想法就是吧问题分成两个大致相等的子问题，然后递归地对它们求解，这是“分”的阶段。“治”阶段就是将两个子问题的解修补到一起并可能再做些少量的附加工作，最后得到整个问题的解。

    在我们的例子中，最大子序列的和只可能出现在3个地方：

1. 出现在输入数据的左半部分

2. 出现在输入数据的右半部分

3. 跨越输入数据的中部而位于左右两个部分

    前两种情况可以递归求解，第三种情况的最大和可以通过求出前半部分（包含前半部分的最后一个元素）的最大和以及后半部分（包括后半部分的第一个元素）的最大和，再将二者相加得到。作为例子，考虑以下输入：

    其中，前半部分的最大子序列和为19（A2~A3），而后半部分的最大子序列和为21（A6～A7）。前半部分包含其最后一个元素的最大和是15（A2～A4），后半部分包含第一个元素的最大和是20（A5～A7）。因此，跨越这两部分的这个子序列才是拥有最大和的子序列，和为15+20=35（A2～A7）。于是出现了下面这种算法：

    算法三：

    有必要对算法三的程序进行一些说明。递归过程调用的一般形式是传递输入的数组和左右边界，它们界定了数组要被处理的部分。第2～8行处理基准情况，让递归调用有退出的机会。如果left==right，那么只有一个元素，并且当该元素非负时，它就是最大子序列。第11、12行执行两个递归调用。我们可以看到，递归调用总是对小于原问题的问题进行，不过程序中的小扰动有可能破坏这个特性。14～20行，22～28行分界处左右两边的最大子序列和，这两个值的和就有可能是整个序列中的最大子序列和。第31行调用max3方法，求出这三种情况下的最大值，该值即为整个序列的最大子序列和。

    显然，算法三需要比设计前两种算法付出更多的编程努力，看上去前面两种算法的代码量要比算法三少许多，然而，程序短并不意味着程序好。测试表明，除较小的输入量外，算法三比前两个算法明显要快。现在来分析以下算法三的时间复杂度。

    令T(N)是求解大小为N的最大子序列和问题所花费的时间。如果N=1，则算法3执行程序第2～8行花费某个常数时间，我们称之为一个时间单位。于是T(1)=1，否则，程序必须执行两个递归调用，即在14～28行之间的两个for循环以及几个小的簿记量，如10、14行。这两个for循环总共接触到A1~An中的每个元素，而在循环内部的工作量是常量，于是14～28行花费的时间为O(N)。从2～10、14、22和31行上的程序的工作量是常量，从而与O(N)相比可以忽略。其余就剩下11～12行上运行的工作。这两行求解大小为N/2的子序列问题（假设N为偶数）。因此，这两行每行花费T(N/2)个时间单元，共花费2T(N/2)个时间单元。因此，算法三花费的总时间为2T(N/2)+O(N)。于是我们得到方程组：

    为了简化计算，我们可以用N代替上面方程中的O(N)项；由于T(N)最终还是要用大O表示，因此这么做并不影响答案。现在，如果T(N) = 2T(N/2) + N，且T(1) = 1，那么T(2) = 4 = 2*2；T(4) = 12 = 4*3；T(8) = 32 = 8*4；T(16) = 80 = 16*5。用数学归纳法可以证明若N=2^k，那么T(N) = 2^k * (k+1) = N * (k+1) = N(logN + 1) = NlogN + N = O(NlogN)。即算法三的时间复杂度为O(NlogN)，这明显小于算法二的复杂度O(N2)，因此算法三会更快的得出结果。

    这个分析假设N是偶数，否则N/2就不确定了。通过该分析的递归性质可知，实际上只有当N是2的幂时结果才是合理的，否则我们最终要得到大小不是偶数的子问题，方程就是无效的了。当N不是2的幂时，我们多少需要更加复杂一些的分析，但是大O的结果还是不变的。

更优秀的算法

    虽然算法三已经足够优秀，将时间复杂度由O(N2)降低为O(NlogN)，但是，这并不是最优秀的，下面介绍针对这个问题更优秀的解法。

    算法四：

    很显然，此算法的时间复杂度为O(N)，这小于算法三中的时间复杂度O(NlogN)，因此，此算法比算法三更快！方法固然已给出，但是要明白为什么此方法能用，还需多加思考。

    在算法一和算法二中，i代表子序列的起点，j代表子序列的终点。碰巧的是，我们不需要知道具体最佳的子序列在哪里，那么i的使用可以从程序上被优化，因此在设计算法的时候假设i是必需的，而且我们想改进算法二。一个结论是：如果a[i]是负数，那么它不可能代表最优序列的起点，因为任何包含a[i]的作为起点的子序列都可以通过使用a[i+1]作为起点得到改进。类似的，任何负的子序列也不可能是最优子序列的前缀（原理相同）。如果在内循环中检测到从a[i]到a[j]的子序列的和是负数，那么可以向后推进i。关键的结论是：我们不仅能够把i推进到 i+1，而且实际上我们还可以把它一直推进到 j+1。为了看清楚这一点，我们令 p 为 i+1 和 j 之间的任意一下标。开始于下标 p 的任意子序列都不大于在下标i开始并包含从 a[i] 到 a[p-1] 的子序列的对应的子序列，因为后面这个子序列不是负的（即j是使得从下标 i 开始，其值成为负值的序列的第一个下标）。因此，把 i 推进到 j+1 是没有风险的：我们一个最优解也不会错过。

    这个算法是许多聪明算法的典型：运行时间是明显的，但正确性却不那么容易就能看出来。对于这些算法，正式的正确性证明（比上面分析更加正式）几乎总是需要的；然而，及时到那时，许多人仍然还是不信服。此外，许多这类算法需要更有技巧的编程，这导致更长的开发过程。不过，当这些算法正常工作时，它们运行得很快！而我们将它们和一个低效但容易实现的蛮力算法通过小规模的输入进行比较可以测试到大部分的程序原理。

    该算法的一个附带优点是：它值对数据进行一次扫描，一旦a[i]被读入并处理，它就不再需要被记忆。因此，如果数组在磁盘上活通过网络传送，那么它就可以被按顺序读入，在主存中不必存储改数组的任何部分。不仅如此，在任意时刻，算法都能对它已经读入的数据给出子序列问题的正确答案（其他算法不具备这个特性）。具有这种特性的算法叫做“联机算法”。仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法。