分治法求最大子数组和

引入：
暴力枚举法：

"""
1.建立一个起始下标和一个终止下标，作为每一段子数组的起始下标和终止下标
2.建立一个变量用来承接在运算过程中的子数组和
3.当运算时当前子数组和大于已计算的子数组和，就更新该变量
"""
def Max_Arr(arr):	# 暴力枚举法计算最大子数组和
	pre = 0	# 起始下标
	rear = len(arr)-1	# 终止下标
	Max_Sum = 0	# 承接最大子数组和的变量
	while pre != len(arr)-1:	# 循环条件
		for pre in range(0,len(arr)):	# 起始下标的范围为0到数组长度-1
		# 终止下标的范围为起始下标到数组长度-1
			for rear in range(pre,len(arr)):	
			# 如果当前子数组和大于已计算的子数组和，更新Max_Sum值
				if Max_Sum < sum(arr[pre:rear+1]):
					Max_Sum = sum(arr[pre:rear+1])
	return Max_Sum	# 返回最大子数组和

优化枚举：用迭代方法求最大子数组和

def Max_Arr(arr):
	Max_Sum = 0
	for pre in range(0,len(arr)):
		for rear in range(pre,len(arr)):
			Max_Sum = max(Max_Sum, sum(arr[pre:rear+1]))
	return Max_Sum

分治思想求解最大子数组和问题：

"""
1.将数组X[low,high]分为左边数组和右边数组两部分
2.左边数组为X[low,mid],右边数组为X[mid+1,high]
3.对左边数组进行逆序遍历，对右边数组进行正序遍历，边遍历边加和，
	用变量S_left指代左边数组最大和，变量S_right指代右边数组变量和
4.Sum指代两边数组最大加和（考虑两数组进行合并时的中间元素）
"""
def CrossingSubArray(X, low, mid, high):    # 求解S3，S3为整个数组的最大值
    S_left = float('-inf')  # 定义S_left为负无穷
    Sum = 0 # 左边数组和暂时初始化为0
    for l in reversed(range(low, mid + 1)): # 对于分解的左边数组逆序遍历
        Sum += X[l] # 边遍历边加和
        S_left = max(S_left, Sum)   # S_left为左边数组的最大值
    S_right = float('-inf') # 定义S_right为负无穷
    Sum = 0 # 右边数组和暂时初始化为0
    for r in range(mid + 1, high + 1):  # 对于分解的右边数组正序遍历
        Sum += X[r] # 边遍历边加和
        S_right = max(S_right, Sum) # S_right为右边数组的最大值
    S3 = S_left + S_right   # 整个数组的最大值为S3
    return S3   # 返回S3


def MaxSubArray(X, low, high):  # 求解最大子数组和
    if low == high: # 如果low下标和high下标相等，说明数组只有一个元素
        return X[low]   # 直接返回X[low]即为最大子数组和
    else:
        mid = (low + high) // 2 # mid下标向下取整
        S1 = MaxSubArray(X, low, mid)   # 对左边数组递归MaxSubArray函数
        S2 = MaxSubArray(X, mid + 1, high)  # 对右边数组递归MaxSubArray函数
        S3 = CrossingSubArray(X, low, mid, high)    # 调用CrossSubArray函数
        S_max = max(S1, S2, S3) # S_max即为最大子数组和
        return S_max    # 返回最大子数组和


if __name__ == '__main__':
    X = [1, -2, 4, 5, -2, 8, 3, -2, 6, 3, 7, -1]
    Max = MaxSubArray(X, 0, len(X) - 1)
    print(Max)

最大子数组问题里面的CrossSubArray函数所采用的方法与归并排序一致，想了解分而治之思想下的归并排序可参考我的另一篇文章分而治之思想下的归并排序