最大子序列和问题

最大子序列和问题是「数据结构与算法分析」一书开篇提出的问题,问题的描述是这样的:
给定N个整数,求其中子序列之和的最大值。如果所有整数均为负数,那么最大子序列之和为0。


那么最简单的方法,当然也是最缓慢的一种算法便是暴力求解法了,这种方法的思路是进行穷举,将每一种可能性都计算出来与当前的最大值进行比较,如果大于该最大值,就将最大值更新为新计算出来的值,代码如下:

易知该算法的时间复杂度为O(N3)。
显然时间复杂度这么高的算法是不可以被接受的,因此有必要寻找一个更为简单高效的方法。书中紧接着给出了一个递归算法,该算法的时间复杂度为O(NlogN),显然它比前一个算法要好太多。那么该算法是如何实现的呢?
首先我们知道:一个数组的最大子序列,要么出现在这个数组的前一半,要么出现在这个数组的后一半,要么横跨这个数组的左右两半,由两半的最大值求和得到。因此我们就可以缩小这个问题的规模,将这个问题转化为:求前后两半以及中间数组的子序列的最大值,然后将这三个值的最大值作为整个数组的最大值。该问题又可以不断细分,这便是递归分治的思想。

所以该算法的源代码如下:

该算法由于思路比较清晰,因此实现起来也比较简单,效果也很好,可以说是一种很不错的算法了。但是文中还介绍了一个几乎完美的算法,代码如下:

说实话,这个算法虽然实现很简单,但是想到却很困难,尤其是判断thisSum是否大于0并将小于0的thisSum置0这一步,可以保证最大子序列的首项一定是一个正数(请仔细思考一下为什么)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注