动态规划解决最大子数组和问题

题目描述
给定一个整数数组 nums，请找出一个具有最大和的连续子数组（子数组至少包含一个元素），并返回其最大和。

示例：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

解题过程循序渐进讲解

步骤1：理解问题与暴力解法
我们需要找到连续子数组的最大和。最直观的方法是枚举所有可能的连续子数组，计算它们的和，并记录最大值。
对于一个长度为 n 的数组，连续子数组的个数是 O(n²) 级别（起点 i 从 0 到 n-1，终点 j 从 i 到 n-1），对每个子数组求和需要 O(n) 时间，总时间复杂度为 O(n³)。可以通过前缀和优化到 O(n²)，但依然不够高效。

步骤2：动态规划思路引入
动态规划通常适用于具有“最优子结构”的问题。我们定义状态：
dp[i] 表示以第 i 个元素结尾的连续子数组的最大和。
注意这里 dp[i] 不是前 i 个元素的最大子数组和，而是必须包含第 i 个元素，这样才能保证连续性，并利用之前的状态。

步骤3：状态转移方程推导
考虑如何从 dp[i-1] 得到 dp[i]：

• 如果 dp[i-1] > 0，那么将 nums[i] 接在以 i-1 结尾的最大和子数组后面，可以得到更大的和，即 dp[i] = dp[i-1] + nums[i]。
• 如果 dp[i-1] ≤ 0，那么 dp[i-1] 对 nums[i] 没有增益，不如从 nums[i] 重新开始一个新的子数组，即 dp[i] = nums[i]。

综合两种情况，状态转移方程为：
dp[i] = max(nums[i], dp[i-1] + nums[i])

步骤4：初始条件与计算顺序
初始条件：当 i=0 时，只有一个元素，dp[0] = nums[0]。
然后从 i=1 到 n-1 依次计算 dp[i]。

步骤5：获取最终结果
dp 数组中的最大值就是整个数组的连续子数组的最大和，即 max(dp[0], dp[1], ..., dp[n-1])。

步骤6：空间优化
注意到 dp[i] 只依赖于 dp[i-1]，因此不需要保存整个 dp 数组，只需用一个变量 cur_max 记录当前以 i 结尾的最大和，再用另一个变量 global_max 记录历史最大值，在遍历过程中更新即可。空间复杂度从 O(n) 降为 O(1)。

步骤7：示例逐步演算
以 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例：

初始化：cur_max = nums[0] = -2, global_max = -2

i=1: cur_max = max(1, -2+1) = 1, global_max = max(-2, 1) = 1
i=2: cur_max = max(-3, 1+(-3)) = -2, global_max = max(1, -2) = 1
i=3: cur_max = max(4, -2+4) = 4, global_max = max(1, 4) = 4
i=4: cur_max = max(-1, 4+(-1)) = 3, global_max = max(4, 3) = 4
i=5: cur_max = max(2, 3+2) = 5, global_max = max(4, 5) = 5
i=6: cur_max = max(1, 5+1) = 6, global_max = max(5, 6) = 6
i=7: cur_max = max(-5, 6+(-5)) = 1, global_max = max(6, 1) = 6
i=8: cur_max = max(4, 1+4) = 5, global_max = max(6, 5) = 6

最终结果 global_max = 6。

步骤8：代码实现（Python）

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

步骤9：复杂度分析
时间复杂度：O(n)，只需一次遍历数组。
空间复杂度：O(1)，只用了常数个额外变量。

步骤10：相关变种与扩展

• 如果需要返回最大和子数组的起始和结束下标，可以在更新 cur_max 和 global_max 时记录下标。
• 如果数组是环形的（即首尾相连），可以通过分别计算不环形的情况和跨环形的情况来解决。
• 该问题也被称为 Kadane 算法，是动态规划的经典入门题。