def maxSubArray(nums):
    current_max = global_max = nums[0]
    for i in range(1, len(nums)):
        current_max = max(nums[i], current_max + nums[i])
        global_max = max(global_max, current_max)
    return global_max

动态规划解决最大子数组和问题（Maximum Subarray Problem） 最大子数组和问题是一个经典的算法问题，目标是在一个整数数组中找到一个连续子数组，使得其和最大。例如，数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 的最大子数组和为 6 （对应子数组 [4, -1, 2, 1] ）。 1. 问题分析 输入 ：整数数组（可能包含负数）。 输出 ：最大子数组的和（若数组全为负数，则输出最大负数）。 关键点 ：子数组必须是连续的，不能跳跃选择元素。 2. 暴力解法（思路引入） 最直接的方法是枚举所有可能的子数组，计算它们的和，并记录最大值。 子数组数量为 O(n²) ，每个子数组求和需要 O(n) ，总时间复杂度为 O(n³) （可优化到 O(n²) ）。 缺点：效率低，无法处理大规模数据。 3. 动态规划思路 动态规划的核心是定义状态和状态转移方程。我们定义： dp[i] ：表示以第 i 个元素结尾的最大子数组和。 状态转移方程： \[ dp[ i] = \max(nums[ i], \ dp[ i-1] + nums[ i ]) \] 解释：以 i 结尾的最大子数组要么是当前元素本身，要么是当前元素加上以 i-1 结尾的最大子数组。 4. 逐步推导示例 以数组 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例： | 索引 i | nums[ i] | dp[ i ]（以 i 结尾的最大和） | 说明 | |--------|---------|----------------------------|------| | 0 | -2 | -2 | 只有当前元素 | | 1 | 1 | max(1, -2+1)=1 | 从 1 开始新子数组 | | 2 | -3 | max(-3, 1-3)=-2 | 延续前序和 | | 3 | 4 | max(4, -2+4)=4 | 抛弃前序和，从 4 开始 | | 4 | -1 | max(-1, 4-1)=3 | 延续前序和 | | 5 | 2 | max(2, 3+2)=5 | 延续前序和 | | 6 | 1 | max(1, 5+1)=6 | 延续前序和 | | 7 | -5 | max(-5, 6-5)=1 | 延续前序和 | | 8 | 4 | max(4, 1+4)=5 | 延续前序和 | 全局最大值在遍历过程中产生： max(dp[0..8]) = 6 。 5. 优化空间复杂度 由于 dp[i] 只依赖于 dp[i-1] ，我们可以用一个变量 current_max 代替整个 dp 数组： current_max 记录以当前元素结尾的最大和。 global_max 记录全局最大值。 时间复杂度 O(n) ，空间复杂度 O(1) 。 6. 边界情况处理 数组全为负数：算法仍能正确返回最大负数（因为 current_max 会逐个比较负数）。 数组长度为 1：直接返回唯一元素。 7. 总结 核心思想 ：通过局部最优解（以每个位置结尾的最大和）逐步推导全局最优解。 关键技巧 ：状态转移方程中比较“是否抛弃前序结果”。 扩展 ：若需要输出具体子数组范围，可记录起始和结束索引（通过跟踪 current_max 更新时的位置）。