最大子序列问题:给定一整数序列A1, A2,..
14 查阅
参考答案:
例如:
\r\n
整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。
对于这个问题,最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环,依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的,下面给出一个算法复杂度为O(n)的线性算法实现,算法的来源于Programming Pearls一书。
在给出线性算法之前,先来看一个对