最大子序列和-分治法

最大子序列和问题是指在一个序列中找到一个连续的子序列，使得子序列的和最大。分治法是一种解决该问题的有效方法。

具体步骤如下：
1. 将原序列分为两个子序列，分别求出左子序列的最大子序列和、右子序列的最大子序列和以及跨越中点的最大子序列和。
2. 左子序列的最大子序列和、右子序列的最大子序列和以及跨越中点的最大子序列和三者中的最大值即为原序列的最大子序列和。
3. 递归地对左子序列和右子序列进行上述操作，直到序列长度为1。

以下是Python代码示例：

def max_subarray(nums, left, right):
    if left == right:
        return nums[left]
    mid = (left + right) // 2
    left_max = max_subarray(nums, left, mid)
    right_max = max_subarray(nums, mid+1, right)
    cross_max = cross_subarray(nums, left, mid, right)
    return max(left_max, right_max, cross_max)

def cross_subarray(nums, left, mid, right):
    left_sum = float('-inf')
    cur_sum = 0
    for i in range(mid, left-1, -1):
        cur_sum += nums[i]
        left_sum = max(left_sum, cur_sum)
    right_sum = float('-inf')
    cur_sum = 0
    for i in range(mid+1, right+1):
        cur_sum += nums[i]
        right_sum = max(right_sum, cur_sum)
    return left_sum + right_sum

nums = [-2, 11, -4, 13, -5, -2]
print(max_subarray(nums, 0, len(nums)-1)) # 输出：20