最大子数组问题和kadane算法

def max_subarray_brute_force(arr):    max_sum = arr[0] # assumes arr has a length    # iterate over all possible subarrays    for i in range(len(arr)):        for j in range(i, len(arr)):            current_sum = 0            # sum the elements of the subarray arr[i:j+1]            for k in range(i, j + 1):                current_sum += arr[k]            # update max_sum if the current sum is greater            max_sum = max(max_sum, current_sum)    return max_sumprint(max_subarray_brute_force([-2, -3, 4, -1, -2, 1, 5, -3]), "== 7")

def max_subarray_optimized(arr):    max_sum = arr[0]  # assumes arr has a length    # iterate over all possible starting points of the subarray    for i in range(len(arr)):        current_sum = 0        # sum the elements of the subarray starting from arr[i]        for j in range(i, len(arr)):            current_sum += arr[j]            # update max_sum if the current sum is greater            max_sum = max(max_sum, current_sum)    return max_sum

def max_crossing_sum(arr, left, mid, right):    # left of mid    left_sum = float('-inf')    current_sum = 0    for i in range(mid, left - 1, -1):        current_sum += arr[i]        left_sum = max(left_sum, current_sum)    # right of mid    right_sum = float('inf')    current_sum = 0    for i in range(mid + 1, right + 1):        current_sum += arr[i]        right_sum = max(right_sum, current_sum)    # sum of elements on the left and right of mid, which is the maximum sum that crosses the midpoint    return left_sum + right_sumdef max_subarray_divide_and_conquer(arr, left, right):    # base case: only one element    if left == right:        return arr[left]    # find the midpoint    mid = (left + right) // 2    # recursively find the maximum subarray sum for the left and right halves    left_sum = max_subarray_divide_and_conquer(arr, left, mid)    right_sum = max_subarray_divide_and_conquer(arr, mid + 1, right)    cross_sum = max_crossing_sum(arr, left, mid, right)    # return the maximum of the three possible cases    return max(left_sum, right_sum, cross_sum)def max_subarray(arr):    return max_subarray_divide_and_conquer(arr, 0, len(arr) - 1)print(max_subarray([-2, -3, 4, -1, -2, 1, 5, -3]), "== 7")

maxSubArray(nums):    # avoiding type errors or index out of bounds errors    if nums is None or len(nums) == 0:        return 0    max_sum = nums[0]  # max sum can't be smaller than any given element    curr_sum = 0    # Kadane's algorithm    for num in nums:        curr_sum = max(num, curr_sum + num)        max_sum = max(curr_sum, max_sum)    return max_sum