区间动态规划例题：最大子数组和问题（基础版本） 题目描述 给定一个整数数组 nums ，找出一个连续子数组，使得其和最大，并返回这个最大和。例如，输入 nums = [-2,1,-3,4,-1,2,1,-5,4] ，连续子数组 [4,-1,2,1] 的和为 6，是所有子数组中最大的。 解题过程 定义状态 设 dp[i] 表示以第 i 个元素结尾的连续子数组的最大和。注意，这里 dp[i] 必须包含 nums[i] ，因为子数组需要连续。 状态转移方程 对于位置 i ，以 nums[i] 结尾的最大和子数组有两种可能： 只包含 nums[i] 自身（即此前缀子数组的和为负，不如重新开始）。 包含 nums[i] 并加上以 nums[i-1] 结尾的最大和子数组（即 dp[i-1] + nums[i] ）。 因此，转移方程为： \[ dp[ i] = \max(nums[ i], dp[ i-1] + nums[ i ]) \] 初始化 当 i = 0 时，只有一个元素， dp[0] = nums[0] 。 计算顺序 从左到右遍历数组，依次计算 dp[i] 。 获取结果 最终的最大和不一定以最后一个元素结尾，因此需要遍历所有 dp[i] ，取最大值作为答案。 示例演算 以 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例： i=0 : dp[0] = -2 i=1 : dp[1] = max(1, -2+1) = 1 i=2 : dp[2] = max(-3, 1-3) = -2 i=3 : dp[3] = max(4, -2+4) = 4 i=4 : dp[4] = max(-1, 4-1) = 3 i=5 : dp[5] = max(2, 3+2) = 5 i=6 : dp[6] = max(1, 5+1) = 6 i=7 : dp[7] = max(-5, 6-5) = 1 i=8 : dp[8] = max(4, 1+4) = 5 最大值为 max(dp[0..8]) = 6 ，对应子数组 [4,-1,2,1] 。 关键点 本题是区间动态规划的简化形式，状态定义聚焦于以某点结尾的子问题。 通过比较“重新开始”和“延续前序”两种策略，确保每一步都局部最优。 时间复杂度为 O(n)，空间复杂度可优化至 O(1)（仅保留前一个 dp 值）。