分治法求最大子数组和

求最大子数组和，采用分治的方法实现，先把数组用中点分为左右两个子数组，这样最大和子数组存在三种情况：（1）在左边的子数组；（2）在右边的子数组；（3）跨过中点，左边子数组的右半部分（也可能是全部）和右边数组的左半部分（也可能是全部）。对于前两种情况，无论哪一种，直接递归下去，而第三种情况，可以根据中点继续分成左半部分和右半部分，左边从中点向左求出最大和，右边从中点向右求出最大和，然后相加。这样三种情况就都可以处理了，每次取处理后的最大值就可以了。

# coding:utf-8

# 获取最大值
def get_max(a, b, c):
    if a >= b and a >= c:
        return a
    elif b >= a and b >= c:
        return b
    else:
        return c

# 获取中间最大和
def get_max_cross_subarray(array, low, mid, high):
    left_border = float("-inf")
    left_sum = 0
    i = mid
    left_index = i
    
    # 找出中点到左边界的最大和
    while i >= low:
        left_sum += array[i]
        if left_sum > left_border:
            left_border = left_sum
            left_index = i
        i -= 1
        
    # 找出中点到右边界的最大和
    right_border = float("-inf")
    right_sum = 0
    j = mid + 1
    right_index = j
    while j <= high:
        right_sum += array[j]
        if right_sum > right_border:
            right_border = right_sum
            right_index = j
        j += 1
    
    # 返回最大和即为左边界数组最大和加上右边界数组最大和
    return left_index, right_index, left_border + right_border


# 获取子数组最大和
def get_max_subarray(array, low, high):
    if low == high:
        return (low, high, array[low])
    else:
        mid = int((low+high) / 2)
        left_low, left_high, left_sum = get_max_subarray(array, low, mid)  # 左子数组递归
        right_low, right_high, right_sum = get_max_subarray(array, mid+1, high)  # 右子数组递归
        cross_low, cross_high, cross_num = get_max_cross_subarray(array, low, mid, high)  # 跨中点数组
        if left_sum >= right_sum and left_sum>= cross_num:
            return (left_low, left_high, left_sum)
        elif right_sum >= left_sum and right_sum >= cross_num:
            return (right_low, right_high, right_sum)
        else:
            return (cross_low, cross_high, cross_num)


num = [1, -1, 2, 5, -3, 3, 4, -3]
print(get_max_subarray(num, 0, len(num)-1))