分治策略——最大子数组

分支策略

	方法：
			1.	分解；
			2.	解决；
			3.	合并；
	核心：递归式；

最大子数组

	概念：一个数组中连续索引之间的和最大的子数组；
	问题解决办法：
			    1.	将数组分为左，右，左右交叉数组；
			    2.	单独递归左右交叉数组；
			    3.	统一递归左右数组；

代码部分

1. 解决左右交叉数组的递归问题

#	  	1.	解决左右交叉数组的递归问题
def find_cross_max_subarray(arr, low, middle, high):
    max_right, max_left = 0, 0 # 设置获取右边最大值和左边最大值
    left_sum = -99		# 初始化左边数组最大值
    sums = 0			# 初始化保存左边最大值
 	# 遍历从中间分割部分到头索引的元素
    for i in range(middle, low - 1, -1):
        sums += arr[i]
        if sums > left_sum:
            left_sum = sums
            max_left = i
    right_sum = -99		# 设置最右边数组最大值
    sums = 0			# 初始化保存右边最大值
    # 遍历从中间+1的索引位置到最后一个数组的索引
    for j in range(middle + 1, high + 1):
        sums += arr[j]
        if sums > right_sum:
            right_sum = sums
            max_right = j
    # 返回左边最大值，右边最大值，中间和值
    return max_left, max_right, left_sum + right_sum

2. 解决左边右边和同时解决返回值最大值和最大子数组索引位置

def find_maximum_subarray(arr, low, high):
    if high == low:	# 如果只有一个元素，则直接返回索引位置和该数组元素
        return low, high, arr[low]
    else:
    	# 获取数组的中间索引位置
        middle = (low + high) // 2
        # 递归解决最左边的数组获取最大子数组的索引和最大值
        left_low, left_high, left_sum = find_maximum_subarray(arr, low, middle)
        # 递归解决最右边的数组获取最大子数组的索引和最大值
        right_low, right_high, right_sum = find_maximum_subarray(arr, middle + 1, high)
        # 递归解决交叉部分数组获取最大子数组的索引和最大值
        cross_low, cross_high, cross_sum = find_cross_max_subarray(arr, low, middle, 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

3. 主函数部分

if __name__ == '__main__':
    arrays = [-1, 2, 4, 6, -2, 3, 1, 0]
    print("初始序列", arrays)
    lows, highs, sums = find_maximum_subarray(arrays, 0, len(arrays) - 1)
    print("最大子数组左索引:  {0}\n最大子数组右索引:  {1}\n最大子数组的和值:  {2}".format(lows, highs, sums))

4. 控制台输出部分

初始序列 [-1, 2, 4, 6, -2, 3, 1, 0]
最大子数组左索引:  1
最大子数组右索引:  6
最大子数组的和值:  14