区间动态规划例题：最大子数组和问题（基础版本） 题目描述 给定一个整数数组 nums ，请找出其连续子数组（至少包含一个元素）的最大和，并返回该和。 示例： 输入：nums = [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ] 输出：6 解释：连续子数组 [ 4, -1, 2, 1 ] 的和最大，为 6。 解题过程 问题分析 最大子数组和问题要求找到数组中连续一段元素的和的最大值。由于子数组必须是连续的，我们可以通过动态规划来记录以每个位置结尾的子数组的最大和，从而避免重复计算。 定义状态 设 dp[i] 表示以第 i 个元素结尾的连续子数组的最大和。注意，这里 dp[i] 必须包含 nums[i] ，以保证子数组的连续性。 状态转移方程 对于位置 i ，以 nums[i] 结尾的最大和子数组有两种可能： 只包含 nums[i] 自身（即从 i 开始的新子数组）； 包含 nums[i] 并接在以 i-1 结尾的最大和子数组之后。 因此，转移方程为： \[ dp[ i] = \max(nums[ i], \ dp[ i-1] + nums[ i ]) \] 这一步的核心是判断是否放弃前面的累加和（当 dp[i-1] < 0 时）。 初始化与遍历 初始化 dp[0] = nums[0] ，因为第一个元素只能自成子数组。 从 i = 1 开始遍历数组，计算每个 dp[i] 。 同时维护一个变量 maxSum ，记录所有 dp[i] 中的最大值。 举例说明 以 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例： i=0 : dp[0] = -2 , maxSum = -2 i=1 : dp[1] = max(1, -2+1) = 1 , maxSum = 1 i=2 : dp[2] = max(-3, 1-3) = -2 , maxSum = 1 i=3 : dp[3] = max(4, -2+4) = 4 , maxSum = 4 i=4 : dp[4] = max(-1, 4-1) = 3 , maxSum = 4 i=5 : dp[5] = max(2, 3+2) = 5 , maxSum = 5 i=6 : dp[6] = max(1, 5+1) = 6 , maxSum = 6 后续计算中 maxSum 不再更新，最终结果为 6。 复杂度分析 时间复杂度：O(n)，只需遍历一次数组。 空间复杂度：O(n)，可优化至 O(1)（仅保留前一个 dp 值）。