算法导论程序3--最大子数组问题（Python）

寻找最大子数组问题：

给定数组A：寻找A中的和最大的非连续子数组。我们称这样的连续子数组为最大子数组（maximum subarray）

使用分治策略的求解方法：

假定我们要寻找子数组A[low...high]的最大子数组。使用分治技术意味着我们要将子数组划分为两个规模尽量相等的子数组。也就是，找到子数组的中央位置，比如mid，然后考虑求解两个子数组A[low...mid]和A[mid+1...high]。A[low...high]的任何连续子数组A[i ...j]所处的位置必然是一下三种情况之一：

1.完全位于子数组A[low...mid]中，因此low<=i<=j<=mid

2.完全位于子数组A[mid+1...high]中，因此mid<i<=j<=high

3.跨越了中点，因此low<=i<=mid<j<=high

我们可以递归地求解A[low...mid]和A[mid+1...high]的最大子数组。剩下的全部工作就是寻找跨越中点的最大子数组，然后在三种情况中选取最大者。

def find_max_crossing_subarray(A,low,mid,high):
    left_sum = float("-inf")
    sum = 0
    max_left = 0
    max_right = 0
    for i in range(mid,low-1,-1):
        sum = sum + A[i]
        if sum > left_sum:
            left_sum = sum
            max_left = i
    right_sum = float("-inf")
    sum = 0
    for j in range(mid+1,high+1):
        sum = sum + A[j]
        if sum > right_sum:
            right_sum = sum
            max_right = j
    return [max_left,max_right,left_sum+right_sum]


import math
def find_maximum_subarray(A,low,high):
    if high == low:
        return (low,high,A[low])
    else:
        mid = math.floor((low+high)/2)
        [left_low,left_high,left_sum] = find_maximum_subarray(A,low,mid)
        [right_low,right_high,right_sum] = find_maximum_subarray(A,mid+1,high)
        [cross_low,cross_high,cross_sum] = find_max_crossing_subarray(A,low,mid,high)
        if left_sum >= right_sum and  left_sum >= cross_sum:
            return [left_low,left_high,left_sum]
        elif right_sum >= left_sum and  right_sum >= cross_sum:
            return [right_low,right_high,right_sum]
        else:return [cross_low,cross_high,cross_sum]