LeetCode 152. 乘积最大子数组

约 5 分钟
文章信息 25 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 50-100 LeetCode 热题 100 腾讯 字节 阿里 华为 微软 美团 拼多多 京东 小米 百度 小红书 快手 滴滴 B站 虾皮 商汤 深信服 猿辅导
标签
数组 动态规划

题目描述

✅ 152. 乘积最大子数组

image-20260928194343916

题意分析

从数组中选择一段非空、连续的元素，使它们的乘积最大，返回这个乘积。不能跳过中间元素，也不能用空数组的乘积来替代实际结果。

元素可以是正数、负数或 0。最优区间可能只有一个元素，也可能在数组中途结束，因此答案不一定为正，更不一定包含最后一个元素。题目保证任意连续子数组的乘积都在 32 位整数范围内。

解法：同时维护最大和最小乘积

核心思路

[!blue]

把问题按子数组的结束位置拆开。定义 maxProd 为以当前位置结尾的非空连续子数组的最大乘积，minProd 为同一范围内的最小乘积；全局答案再取所有结束位置的 maxProd 中的最大值。

为什么还要保存最小值？当前数为正时，乘法保持大小关系，原最大值延伸后仍最有可能最大；当前数为负时，乘法会反转大小关系，原最小的负乘积反而可能变成最大的正乘积。因此不能像最大子数组和那样，只保留一个最大状态。

对当前数 num，任何以它结尾的连续子数组只有两种形态：只包含当前数，或者在某个以前一位置结尾的子数组后接上当前数。后一种形态中，乘以固定的 num 后，极值一定来自原来的最大值或最小值，所以只需比较 num、oldMax * num、oldMin * num 三个候选，分别得到新的最大与最小乘积。

把 num 本身作为候选，允许随时从当前元素重新开始。当前数为 0 时，两个结束于此处的极值自然都变成 0；之后遇到新元素，仍可通过选择它本身越过这个零重新起步，无需单独分段。

两个新状态都依赖上一轮的极值，更新前必须保存 oldMax、oldMin，避免第二次更新误用第一次的新结果。初始状态和答案都取第一个元素，才能保证始终选择非空子数组。

解题步骤

  1. 用 nums[0] 初始化 maxProd、minProd 和全局答案 ans。
  2. 从第二个元素开始，先保存上一位置的 oldMax、oldMin。
  3. 计算当前数本身、当前数乘旧最大值、当前数乘旧最小值，取其中最大值更新 maxProd，最小值更新 minProd。
  4. 用新的 maxProd 更新 ans，保留所有已经处理的结束位置中的最好结果。
  5. 遍历结束后返回 ans，而不是仅返回最后一轮的 maxProd。

代码实现

class Solution {
    public int maxProduct(int[] nums) {
        int maxProd = nums[0];
        int minProd = nums[0];
        int ans = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            // 两个新状态都依赖旧最大、旧最小，先保存后再更新。
            int oldMax = maxProd;
            int oldMin = minProd;

            // 负数会让最大乘积和最小乘积角色互换。
            maxProd = Math.max(num, Math.max(oldMax * num, oldMin * num));
            minProd = Math.min(num, Math.min(oldMax * num, oldMin * num));
            ans = Math.max(ans, maxProd);
        }

        return ans;
    }
}

func maxProduct(nums []int) int {
    maxProd := nums[0]
    minProd := nums[0]
    ans := nums[0]

    for i := 1; i < len(nums); i++ {
        num := nums[i]
        // 两个新状态都依赖旧最大、旧最小，先保存后再更新。
        oldMax := maxProd
        oldMin := minProd

        // 当前数为负时，旧最小值可能变成新的最大值。
        maxProd = maxInt(num, maxInt(oldMax*num, oldMin*num))
        minProd = minInt(num, minInt(oldMax*num, oldMin*num))
        ans = maxInt(ans, maxProd)
    }

    return ans
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

func minInt(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(n)$，数组只遍历一次。
  • 空间复杂度：$O(1)$，只维护两个滚动状态和答案。

关键点总结

[!green]

  • “以当前位置结尾”保证连续性，才能从前一位置的状态直接延伸。
  • 乘以负数会交换大小关系，所以最大和最小两个极值都必须保留。
  • 当前数单独成为候选，负责重新选起点，也让 0 的处理自然融入递推。

易错点总结

[!yellow]

  • 只保留最大乘积，会丢失随后遇到负数时能够反转成最大值的负乘积。
  • 把答案初始化为 0，等于允许不选任何元素，会错误处理只有负数且最佳结果为负的情况。
  • 转移漏掉当前数本身，就无法舍弃前面的不利乘积，也无法在 0 后重新开始。
  • 用更新后的 maxProd 计算 minProd，会把当前元素重复计入，两个状态都应使用上一轮值。
  • 直接返回最后的局部最大乘积，会漏掉已经在更早位置结束的最优子数组。

相似题目

题目 难度 关联与区别
53. 最大子数组和 中等 同样维护以当前元素结尾的最优值，但乘法遇负数会交换最大与最小状态。
1567. 乘积为正数的最长子数组长度 中等 同样跟踪负数对乘积符号的影响，原题只求正乘积区间长度，本题还比较乘积数值。
918. 环形子数组的最大和 中等 维护以当前位置结尾的最优连续区间；本题负数会交换最大与最小乘积状态，该题同时计算最小区间和处理首尾相接。
1186. 删除一次得到子数组最大和 中等 维护以当前位置结尾的最优连续区间；本题负数会交换最大与最小乘积状态，该题增加已经删除一次的状态。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/75102165
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！