使用分治算法求最大子段和，输出最大和

最大子段和问题可以使用分治算法来求解，具体思路如下：

1. 将原问题分成两个子问题，分别是左区间和右区间，递归求解这两个子问题；
2. 对于左区间和右区间，分别求出最大子段和，记为 left_sum 和 right_sum；
3. 考虑跨越左右区间的最大子段和，可以从中间位置向左右两边扩展，分别求出左半部分的最大后缀和 left_max 和右半部分的最大前缀和 right_max，然后将它们相加得到跨越左右区间的最大子段和 cross_sum；
4. 最终的最大子段和可以是左区间的最大子段和 left_sum、右区间的最大子段和 right_sum、或者跨越左右区间的最大子段和 cross_sum 中的最大值。

下面是使用 Python 代码实现分治算法求解最大子段和问题：

def max_cross_sum(nums, left, mid, right):
    left_max = float('-inf')
    s = 0
    for i in range(mid, left-1, -1):
        s += nums[i]
        left_max = max(left_max, s)
    right_max = float('-inf')
    s = 0
    for i in range(mid+1, right+1):
        s += nums[i]
        right_max = max(right_max, s)
    return left_max + right_max

def max_subarray(nums, left, right):
    if left == right:
        return nums[left]
    mid = (left + right) // 2
    left_sum = max_subarray(nums, left, mid)
    right_sum = max_subarray(nums, mid+1, right)
    cross_sum = max_cross_sum(nums, left, mid, right)
    return max(left_sum, right_sum, cross_sum)

nums = [1, -3, 2, 1, -1]
print(max_subarray(nums, 0, len(nums)-1))  # 输出 3

上述代码的时间复杂度是 O(nlogn)，其中 n 是数组的长度。