最大连续子序列和(二)
lmax,recursionMax(X,l,m),recursionMax(X,m+1,u))
16 def maxSeqSum4(X):
17 '''maxSeqSum4 O(nlogn)'''
18 return recursionMax(X,0,len(X)-1)
复制代码
原问题的规模为T(n)，用上面的递归解法，T(n) = 2T(n/2)+O(n)=O(nlogn)
4、哇哦~O(n)
1977年UIF Grenander把这个问题告诉了CMU的Michael Shmos，Michael Shmos连夜想出来了上面的O(nlogn)算法，并与Jon Bentley分享，他们当时认为这是最好的算法了，可是几天后，Shmos在CMU的一个报告会上向统计学家Jay Kadane描述了这个问题，Kadane几分钟就想出来一个O(n)的算法，太牛叉啦~
Kadane的O(n)的算法只需要一个扫描数组X一次，扫描的过程记录一个当前最大值maxsofar与一个以当前元素为右端点的最大值maxendinghere，在扫描的过程中如果maxendinghere比0小，那就从开始重新记录。算法如下：
复制代码
1 def maxSeqSum5(X):
2 '''maxSeqSum5 O(n)'''
3 maxsofar = maxendinghere = 0
4 for i in xrange(len(X)):
5 maxendinghere += X[i]
6 if maxendinghere < 0:
7 maxendinghere = 0
8 maxsofar = max(maxsofar,maxendinghere)
9 return maxsofar
复制代码
这已经是最优的解法了，任何正确的算法必须是O(n)复杂度的。假设最大和子数组为X[i,..,j]，那么为了确定X[i,..,j]最大，我们必须遍历X[0,i)和X(j,n)的所有元素，不论X[1,i)多么的小，都不能排除加上X[0]后变得超级大，从而最大子数组成了X[0,...,j]。
前面的几个解法，都只是求出了最大值，并没有指出数组的范围，但找出来也很容易，下面的代码改进了一下O(n)的解法，同时返回子数组的下标起点和终点：
复制代码
1 def maxSeqSum6(X):
2 '''maxSeqSum5 O(n)'''
3 # s1,su is the start and end of so far ,
4 # el,eu is start and end of endinghere
5 # take care that the subvector is X[s1,su), not X[s1,su]
6 maxsofar = maxendinghere = 0
7 sl = su = el = eu = 0
8 for i in xrange(len(X)):
9 maxendinghere += X[i]
10 if maxendinghere < 0:
11 maxendinghere = 0
12 el = eu = i+1
13 else:
14 eu += 1
15 if maxsofar < maxendinghere:
16 maxsofar = maxendinghere
17 sl = el
18 su = eu
19 return maxsofar,sl,su-1
复制代码
只有得到不能再优化的解法，那些大牛才能安心的睡觉。