跳到主要内容

乘积最大子数组

为什么乘积问题不能只维护最大值？​

  • 问题: 求乘积最大的连续子数组 (152);
  • 原因: 数组含负数, 一个很小的负数乘上负数会变成很大的正数;
  • 结论: 只记录最大值会丢掉"由最小值翻盘"的候选, 必须同时保留最小值;

如何同时维护最大值和最小值？​

  • 状态: dpMax[i]、dpMin[i] 为以 nums[i] 结尾的乘积最大、最小的子数组;
  • 候选: 上一个最大乘当前、上一个最小乘当前、只取当前元素三类;
  • 方程:
    • dpMax[i] = max(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]);
    • dpMin[i] = min(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]);
  • 初值: dpMax[0] = dpMin[0] = nums[0];
  • 答案: max(dpMax);
const maxProduct = (nums) => {
  let max = nums[0];
  let min = nums[0];
  let res = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const candidates = [max * nums[i], min * nums[i], nums[i]];
    max = Math.max(...candidates);
    min = Math.min(...candidates);
    res = Math.max(res, max);
  }
  return res;
};
  • 注意: 两个状态必须用同一轮的旧值同步更新, 不要先改 max 再算 min;
  • 复杂度: 时间 O(n), 空间 O(1);

遇到 0 时状态会怎样？​

  • 效果: 任何数乘 0 都是 0, 候选里包含 nums[i] = 0, 相当于从当前位置重新开始;
  • 无需特判: 转移方程自动把 0 当作新的分界点;