《算法导论》一书中演示分治算法的第二个例子，第一个例子是递归排序，较为简单。寻找maximum subarray稍微复杂点。
题目是这样的：给定序列x = [1, -4, 4, 4, 5, -3, -4, 9, 6 - 4, 6, 4, 3, -5]；寻找一个连续的子序列，使得其和是最大。
这个题目有意义的地方在于，序列X的元素有正有负。
思路很简单，把序列分为相同的两部分A和B，在其内寻找maximum subarray，那么maximum subarray有可能在A中，也有可能在B中，也有可能横跨A和B。
所以，一、递归地在A，B中寻找最大子序列；二、在序列X中寻找横跨中间点的maximum subarray；
最后，比较三者，哪个打，结果就是哪个喽。
代码如下：
在序列X中寻找横跨中间点的maximum subarray
def findmaxcrosssubarr(arr, low, mid, high):
lefmax = -10000
sum_l = 0
i = mid
index_l=mid
index_r=mid
while (i > low):
sum_l += arr[i]
if sum_l > lefmax:
lefmax = sum_l
index_l = i
i -= 1
rightmax = -10000
sum_r = 0
j = mid + 1
while (j < high):
sum_r += arr[j]
if sum_r > rightmax:
rightmax = sum_r
index_r = j
j += 1
return lefmax + rightmax, index_l, index_r
递归地寻找maximum subarray
def maxsubarr(arr, low, high):
if high-low < 1:
return arr[low], low, high
mid = (high+low)/2
value_l, low_l, high_l = maxsubarr(arr, low, mid)
value_r, low_r, high_r = maxsubarr(arr, mid+1, high)
value_m, low_m, high_m = findmaxcrosssubarr(arr, low, mid, high)
maxvalue = max(value_l, value_m, value_r)
if maxvalue==value_l:
return value_l, low_l ,high_l
if maxvalue==value_r:
return value_r, low_r, high_r
if maxvalue==value_m:
return value_m, low_m, high_m
感想：递归解决问题的几个考虑的点：1、做好问题的分解，形成递归（就是说子问题和原问题是同类型的）后，就可以假设可以解决了，最多就是把初始情况解决了；2、子问题合并回原问题比较有技巧性，需要多思考。
当然，也可以使用暴力解法，遍历所有可能的情况，通过比大小，找出答案。
def brutemaxsub(arr):
m=-10000
s,t=0,0
for i in range(len(arr)):
j=i
maxj=0
while j<len(arr):
maxj+=arr[j]
if maxj>m:
m=maxj
s=i
t=j
j+=1
return m,s,t
当然啦，这个问题也可以在线性时间内解决。
代码如下，有点绕。
def maxsub(arr):
m=m1=arr[0]
s,t=s1,t1=0,0
i = 1
while i<len(arr):
m1+=arr[i]
if m1>m:
s=s1
t=t1=i
m=m1
if m1<0:
s1=i+1
t1=i + 1
m1=0
i+=1
return m,s,t