分别用穷举法、分治法、动态规划法编程实现最大子段和问题

**最大子段和问题**是一个经典的动态规划问题，可以使用三种方法来解决，分别是穷举法、分治法（Kadane's Algorithm）以及动态规划。下面我会简要介绍每种方法的基本思想，并给出简单的Python代码实现。

### 穷举法（Brute Force）
这是一种简单但效率较低的方法，通过枚举所有的子数组，找出最大和的那个。

def max_subarray_bruteforce(arr):
    max_sum = float('-inf')
    current_sum = 0
    for i in range(len(arr)):
        current_sum = max(arr[i], current_sum + arr[i])
        max_sum = max(max_sum, current_sum)
    return max_sum

# 测试
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_bruteforce(arr))

### 分治法（Kadane's Algorithm）
这种方法更高效，适用于连续子数组的情况。它维护两个变量：全局最大子数组和当前子数组的最大和。

def max_subarray_kadanes_algorithm(arr):
    max_global = curr_max = arr[0]
    for num in arr[1:]:
        curr_max = max(num, curr_max + num)
        max_global = max(max_global, curr_max)
    return max_global

# 测试
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_kadanes_algorithm(arr))

### 动态规划
这是最常用且高效的解决方案，通过创建一个二维数组记录每个位置的最大子数组和。

def max_subarray_dp(arr):
    dp = [0] * len(arr)
    dp[0] = arr[0]
    for i in range(1, len(arr)):
        dp[i] = max(arr[i], dp[i-1] + arr[i])
    return max(dp)

# 测试
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dp(arr))

在这三种方法中，动态规划法通常是最优解，因为它避免了不必要的重复计算。