最大连续子序列
最大连续子序列是“由原序列中连续元素构成的所有序列里，元素和最大的”，比如\([11, -4, 13, -5, 5,-1]\)的最大连续子序列有\([11,-4,13]\)和\([11,-4,13,-5,5]\)两个。这里规定空序列不能作为问题的输入，非空序列的最大连续子序列至少包含1个元素。那么对于全负序列，其最大连续子序列仅包含其中的最大值。然后来寻找其分治算法，设\(L=[0,…,n]\)为序列，将其尽量等长分为非空的\(L_1=L[0,…,k]\)与\(L_2=L[k+1,…,n]\)。如下情况至少成立1种：
a) \(L\)存在可作为\(L_1\)最大连续子序列的最大连续子序列；
b) \(L\)存在可作为\(L_2\)最大连续子序列的最大连续子序列；
c) \(L\)存在分别在\(L_1,L_2\)中各包含至少1个元素(\(L[k]\)和\(L[k+1]\))的最大连续子序列；
对于上述(a)(b)情况，需分别求解子问题得到解\(s_1,s_2\)。对于上述(c)情况，有一个遍历即可求出一个解的方法，这里以对左半部分的\([…,L[k]]\)的操作为例，给出具体流程如下：
1) 初始化\(i=k,sum=L[k]\)和\(maxSum=sum,maxIdx=i\)；
2) 若\(i==0\)则退出流程，否则\(i=i-1，sum=sum+L[i]\)；
3) 若\(sum\geq maxSum\)，则\(maxSum=sum, maxIdx=i\)；
4) 返回到步骤(2)；
同理对于右半部分\([L[k+1],…]\)也做类似的流程。最后得到左右两边的\(maxIdx\)，分别计为\(maxIdxL,maxIdxR\)。比较\(s_1, s_2, L[maxIdxL,…,maxIdxR]\)三个序列，三者元素和最大的就是原问题的一个解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | def f(arr, i, j): # [i,j) if j == i + 1: return [arr[i]] m = (i + j) // 2 a1 = f(arr, i, m) a2 = f(arr, m, j) i1, s1 = m - 1, arr[m - 1] maxIdx1, maxS1 = m - 1, arr[m - 1] while i1 > 0: i1 -= 1 s1 += arr[i1] if s1 >= maxS1: maxS1 = s1 maxIdx1 = i1 i2, s2 = m, arr[m] maxIdx2, maxS2 = m, arr[m] while i2 < j - 1: i2 += 1 s2 += arr[i2] if s2 >= maxS2: maxS2 = s2 maxIdx2 = i2 a3 = arr[maxIdx1:maxIdx2+1] sum1 = sum(a1) sum2 = sum(a2) sum3 = sum(a3) if max([sum1,sum2,sum3]) == sum1: return a1 if max([sum1,sum2,sum3]) == sum2: return a2 if max([sum1,sum2,sum3]) == sum3: return a3 |
最后分析时间复杂度，其满足\(T(n) = 2T(\frac{n}{2}) + O(n)\)。根据主定理解得\(T(n)=O(nlgn)\)。