分治法求最大子段和并给出最大字段序列

分治法求最大子段和的思路是将问题分成两个子问题，分别求出左半边和右半边的最大子段和，然后再求出跨越中间的最大子段和。最终的最大子段和就是这三个中的最大值。

最大字段序列可以通过记录最大子段和的起始位置和结束位置来得到。具体实现可以参考以下代码：

def max_subarray(nums, left, right):
    if left == right:
        return nums[left], left, right
    
    mid = (left + right) // 2
    left_sum, left_start, left_end = max_subarray(nums, left, mid)
    right_sum, right_start, right_end = max_subarray(nums, mid+1, right)
    
    cross_sum, cross_start, cross_end = max_cross_subarray(nums, left, mid, right)
    
    if left_sum >= right_sum and left_sum >= cross_sum:
        return left_sum, left_start, left_end
    elif right_sum >= left_sum and right_sum >= cross_sum:
        return right_sum, right_start, right_end
    else:
        return cross_sum, cross_start, cross_end

def max_cross_subarray(nums, left, mid, right):
    left_sum = float('-inf')
    sum = 0
    for i in range(mid, left-1, -1):
        sum += nums[i]
        if sum > left_sum:
            left_sum = sum
            max_left = i
    
    right_sum = float('-inf')
    sum = 0
    for i in range(mid+1, right+1):
        sum += nums[i]
        if sum > right_sum:
            right_sum = sum
            max_right = i
    
    return left_sum + right_sum, max_left, max_right

其中，`max_subarray`函数用于求最大子段和，`max_cross_subarray`函数用于求跨越中间的最大子段和。两个函数都是递归实现的。最终的最大子段和和最大字段序列可以通过`max_subarray`函数返回的三个值得到。