Interview Wiki

5分钟阅读

152. 乘积最大子数组（Maximum Product Subarray）

频次 ★★★ · 难度 🟡 · 高频：字节

题目

给定一个整数数组 nums，找到乘积最大的连续子数组（至少包含一个元素），返回其最大乘积。

示例：

输入: nums = [2, 3, -2, 4]
输出: 6
解释: 子数组 [2,3] 乘积最大为 6

思路

双变量法（处理负数）：

  • 因为负数×负数=正数，所以要同时维护最大值和最小值
  • 遇到负数时，最大值和最小值会互换
  • 每一步更新 maxSoFar 和 minSoFar，并记录全局最大值

关键点：遇到 0 时，最大值和最小值都会被重置为 0（或与当前元素比较）。

代码

public int maxProduct(int[] nums) {
    int maxSoFar = nums[0], minSoFar = nums[0], result = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int n = nums[i];
        if (n < 0) {
            int temp = maxSoFar;
            maxSoFar = minSoFar;
            minSoFar = temp;
        }
        maxSoFar = Math.max(n, maxSoFar * n);
        minSoFar = Math.min(n, minSoFar * n);
        result = Math.max(result, maxSoFar);
    }
    return result;
}

复杂度

  • 时间：O(n) — 一次遍历
  • 空间：O(1) — 三个变量

边界条件

  • 数组只有一个元素：三个变量都初始化为该元素，循环不执行，直接返回它本身（无论正负）。
  • 含 0（如 [2,0,3]）：maxSoFar、minSoFar 在遇到 0 时都会被拉到 0（因为 Math.max(0, x*0) 和 Math.min(0, x*0) 都参与比较），相当于”以 0 为界重新开始”，天然正确处理了 0 会截断子数组的情况。
  • 全为负数且个数为偶数：两两相乘为正，maxSoFar/minSoFar 的互换机制能让最终结果捕捉到”整体相乘”是最大值的情况。

变式

  • 53. 最大子数组和 是本题的”加法版”，因为加法不会因符号改变大小关系，只需要一个变量；乘法因为负负得正，必须同时追踪最大值和最小值。
  • 要求返回具体的子数组：额外记录 maxSoFar 更新时对应的起止下标，逻辑和最大子数组和的变式类似。

易错点

  • 遇到负数时必须先交换 maxSoFar、minSoFar，再进行 Math.max/Math.min 更新，顺序反了会用”交换前的值”参与计算，得到错误结果。
  • 不能只维护 maxSoFar 而不维护 minSoFar：当前是负数的最小值乘以下一个负数可能变成全局最大值，漏掉 minSoFar 就丢失了这条路径。

面试追问

  • 为什么必须同时维护最大值和最小值，只维护最大值为什么不行？ 因为负数乘以负数会变成正数，当前的最小值（很可能是一个绝对值很大的负数）如果再乘上一个负数，就可能反超当前的最大值成为新的最大值；只跟踪最大值会丢失这种”由负转正”的路径。
  • 数组中有 0 会不会破坏这个算法？ 不会，0 相当于把乘积”清零重启”，因为 Math.max/Math.min 会把 0 也纳入比较，maxSoFar/minSoFar 遇到 0 后会自然地被拉到 0，效果等同于以 0 为分界点重新开始计算，不需要额外的特判逻辑。

关联题

关系图谱

反向链接