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

摘要 本文分析并演示最大子序列和问题的几种算法，它们都能解决问题，但是时间复杂度却大

相径庭，最后将逐步降低至线性。

算法 子序列和

问题的引入

给定（可能有负数）整数序列A1, A2, A3..., An， 求这个序列中子序列和的最大

值。（为方便起见，如果所有整数均为负数，则最大子序列和为0）。例如：输入整数序列： -2, 11, 8, -4, -1, 16, 5, 0，则输出答案为35，即从A2～A6。

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

切入正题

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

public static int maxSubsequenceSum(int[] a) { int maxSum = 0;

for(int i=0; i

for(int k=0; k<=j; k++) //迭代子序列中的每一个元素，求和

thisSum += a[k]; if(thisSum > maxSum) maxSum = thisSum; } }

return maxSum; }

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

现在来分析以下这个算法的时间复杂度。运行时间的多少，完全取决于第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行上的计算过分的耗费了。下面是在算法一的基础上改进的一种算法： 算法二：

public static int maxSubsequenceSum(int[] a) { int maxSum = 0;

for(int i=0; i

for(int j=i; j maxSum)

maxSum = thisSum; } }

return maxSum; }

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

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

1.

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

2. 3.

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

4. 5.

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

6.