.(Python程序题) 利用分治法求数组连续最大和，例如输入： -2, 3, 4, 1, -1, 7, -3, 7, -6 输出： 18

在 Python 中，可以使用动态规划结合分治的思想来求解数组的连续最大和。这里我们通常会遇到“Kadane’s Algorithm”（卡特兰算法），这是一种高效计算数组中局部和的最大值的方法。下面是简单的实现步骤：

def max_subarray_sum(arr):
    # 初始化最左边界，当前子数组最大和，全局最大和
    left = curr_max = global_max = arr[0]

    for i in range(1, len(arr)):
        # 如果当前元素加上前一个子数组的最大和比当前元素本身大，
        # 则更新当前子数组最大和，否则从当前元素开始构建新的子数组
        curr_max = max(arr[i], curr_max + arr[i])
        
        # 更新全局最大和
        global_max = max(global_max, curr_max)

    return global_max

# 测试输入
arr = [-2, 3, 4, 1, -1, 7, -3, 7, -6]
print(max_subarray_sum(arr))  # 输出: 18

这个算法的核心思想是，无论何时，我们都只关心当前元素和前面最大子数组相加是否能带来更大的和。如果不能，则抛弃前面的部分，从当前元素开始重建一个新的子数组。通过这种方法，我们可以避免在每次迭代时都计算整个数组的和。