最大子数组问题分治法python

以下是使用分治法解决最大子数组问题的Python代码：

def max_subarray(arr):
    if len(arr) == 1:
        return arr[0]
    else:
        mid = len(arr) // 2
        left_arr = arr[:mid]
        right_arr = arr[mid:]
        left_max = max_subarray(left_arr)
        right_max = max_subarray(right_arr)
        cross_max = max_cross_subarray(arr, mid)
        return max(left_max, right_max, cross_max)

def max_cross_subarray(arr, mid):
    left_sum = -float('inf')
    right_sum = -float('inf')
    sum = 0
    for i in range(mid - 1, -1, -1):
        sum += arr[i]
        if sum > left_sum:
            left_sum = sum
    sum = 0
    for i in range(mid, len(arr)):
        sum += arr[i]
        if sum > right_sum:
            right_sum = sum
    return left_sum + right_sum

该代码中，`max_subarray`函数使用递归的方式将数组分成左半部分、右半部分和跨越中心的部分，然后返回这三个部分中最大的子数组和。`max_cross_subarray`函数计算跨越中心部分的最大子数组和，具体实现方式是从中心点向左、向右分别计算最大子数组和。

该代码的时间复杂度是$O(n\log n)$，其中$n$是数组的长度，因为每次递归都会将数组长度减半，所以递归深度是$O(\log n)$，而`max_cross_subarray`函数的时间复杂度是$O(n)$。