./Maximum Subarray

posted by cli on

Maximum Subarray

最近翻看Programming Pearls时注意到一个有意思的练习题,之前几次看的时候居然没有留 意过这个题,实在是罪过,看书太不认真了。这个题是COLUMN 8的Problem 8:

Modify Algorithm 3(the divide-and-conquer algorithm) to run in linear worst-case time.

这里算法要解决的是maximum subarray problem。

分治算法的基本过程可以表述为:solve = merge · (map solve) · divide。书中算法 3就是一个标准的分治算法:先求得左右两个子数组的解ma, mb,以及包含分割点的最大子数 组的和mc,那么原问题的解可以写为:m = max(ma, mb, mc)。当然,递归过程需要basecase, 这里的basecase就是数组长度为0或1的时候。该算法的递推公式是T(n) = 2T(n/2) + O(n), 由Master Theorem可以解得T(n) = O(nlogn)。Problem 8就是要求修改该算法,使时间复杂 度T(n) = O(n)

很容易想到,merge的时间复杂度必须要是O(1)才能得到T(n) = O(n)。估计受Kadane 算法的影响,我当时想了一个小时也没想出该怎么让mergeO(1)内完成,惯性思维在左右 解决思路。后来看了书中给出的提示:

In addition to computing the maximum sum in the region, return information about the maximum vectors ending at each side of the array.

呃…起码指明了方向,让我跳出了惯性思维。如果我们知道了a, b两个子数组两端的最大和, 那么mc只需一个求和就能得到了。

+-----------------------------------+
|       a        |         b        |
+-----------------------------------+

到此,问题还是没有解决,由于是递归过程,我们现在还需要在O(1)时间内求得原数组两端的最大和。 原数组左端的最大和子数组有两种情况:包含在a中,或者包含a。如果包含在a中,那也就是a 左端最大和子数组。如果包含a,那就是a中所有元素的和加上b左端最大和。

现在问题来了,我们要在O(1)时间内求得ab中所有元素的和。仔细想想,我们的递归过程不仅 要返回子数组两端的最大和,还要返回子数组中所有元素的和,这样才能在得到时间复杂度为O(1)merge函数。

我们的solve应该返回如下信息:

struct Answer {
    maxsum, i, j,
    leftsum, leftEnding,
    rightsum, rightStarting,
    totalsum
}

代码就不放了,很容易实现,就是有些繁琐而已。最终的算法的确是O(n),但无论效率还是简洁优雅 都不如Kadane的算法。一开始就接触Kadane算法,估计会和我一样很难想到这个O(n)的分治算法。 算法本身我觉得比Kadane算法好理解,可惜由于惯性思维不是那么容易想到的。