跳到主要内容

最大子数组和

以 nums[i] 结尾的状态如何定义？​

  • 问题: 求和最大的连续子数组 (53);
  • 阶段: 按子数组末端索引划分;
  • 状态: dp[i] 为以第 i 个数结尾的连续子数组的最大和;
  • 锚点意义: 结尾固定后, 子问题才可递推; 不锚定结尾就无法只用一个下标表示连续区间;

如何写出转移方程？​

  • 推导: 若前缀和 dp[i-1] >= 0, 续上它只会更大; 若 dp[i-1] < 0, 不如从当前元素重新开始;
dp[i]={nums[i]dp[i−1]<0dp[i−1]+nums[i]dp[i−1]≥0dp[i] = \begin{cases} nums[i] & dp[i-1] < 0 \\ dp[i-1] + nums[i] & dp[i-1] \geq 0 \end{cases}
  • 等价形式: dp[i] = max(nums[i], dp[i-1] + nums[i]);
  • 答案: max(dp), 不是 dp[i] 本身;
const maxSubArray = (nums) => {
  let prev = nums[0];
  let res = nums[0];
  for (let i = 1; i < nums.length; i++) {
    prev = Math.max(nums[i], prev + nums[i]);
    res = Math.max(res, prev);
  }
  return res;
};
  • 优化: dp[i] 只依赖 dp[i-1], 用滚动变量即可把空间降到 O(1);
  • 复杂度: 时间 O(n), 空间 O(1);

如果要求返回子数组本身怎么办？​

  • 额外记录: 状态转移时同步记录当前子数组起点;
  • 做法: 重新开始时把起点更新为 i, 续接时起点不变; 当 prev 刷新全局最大值时保存区间;
  • 注意: 全为负数时答案取单个最大元素, 起点终点相同;