152. 乘积最大子数组#

大家好，今天我们来聊一道很有意思的题目：乘积最大子数组。这道题乍看简单，但暗藏玄机，因为负数的存在会让问题变得复杂。不过别担心，我们会用最直观的方式来理解它。

🤔 问题是什么？#

给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组的乘积。

比如：

输入：[2,3,-2,4]
输出：6
解释：子数组 [2,3] 有最大乘积 6

plaintext

问题描述#

题目目标#

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组，并返回该子数组对应的乘积。

示例 1#

输入： nums = [2,3,-2,4] 输出： 6 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

🌟 为什么这题很特别？#

让我们先看一个简单的例子：

nums = [1,2,3,4]

plaintext

这种情况很简单，数字都是正的，越乘越大，答案就是 24。

但如果数组包含负数呢？

nums = [2,-3,4]

plaintext

这时情况就变得有趣了：

2 × (-3) = -6
(-3) × 4 = -12
2 × (-3) × 4 = -24
单个数字：2, -3, 4

答案是 4，就是选择单个数字4。

再看一个更有趣的例子：

nums = [2,-3,-4]

plaintext

这时因为负负得正：

2 × (-3) = -6
(-3) × (-4) = 12 ← 这是答案！
2 × (-3) × (-4) = 24

所以答案是 12！

💡 关键发现：负负得正！#

通过上面的例子，我们发现了一个重要特点：

当遇到正数时，希望之前的乘积越大越好
当遇到负数时，希望之前的乘积越小越好（因为负负得正！）

这就是解题的关键：我们需要同时记录两个信息：

到当前位置的最大乘积
到当前位置的最小乘积

🎨 动态规划方案#

让我们定义：

maxDP[i]：以第i个数结尾的最大乘积
minDP[i]：以第i个数结尾的最小乘积

举个例子：nums = [2,-3,-4]

初始：
maxDP[0] = 2    minDP[0] = 2

来到 -3：
maxDP[1] = max(-3, 2×(-3)) = -3
minDP[1] = min(-3, 2×(-3)) = -6

来到 -4：
maxDP[2] = max(-4, -3×(-4), -6×(-4))
         = max(-4, 12, 24)
         = 24
minDP[2] = min(-4, -3×(-4), -6×(-4))
         = min(-4, 12, 24)
         = -4

plaintext

📝 代码实现#

让我们把上面的思路转换成代码：

class Solution {
    public int maxProduct(int[] nums) {
        // 边界情况：若数组为空或 null，无法形成非空子数组，这里返回 0
        if (nums == null || nums.length == 0) return 0;

        // max：表示“以当前位置结尾”的最大乘积
        int max = nums[0];
        // min：表示“以当前位置结尾”的最小乘积（用于处理负数翻转）
        int min = nums[0];
        // result：记录遍历过程中的全局最大乘积
        int result = nums[0];

        // 从第二个元素开始更新状态
        for (int i = 1; i < nums.length; i++) {
            // temp 暂存旧的 max，因为后面计算 min 时仍需要“上一轮 max”
            int temp = max;

            // 计算当前位置的最大值
            // 可能是：当前数、前面最大值×当前数、前面最小值×当前数
            max = Math.max(nums[i], Math.max(max * nums[i], min * nums[i]));

            // 计算当前位置的最小值
            // 同理，最小值也可能来自三种候选：当前数、旧 max*当前数、旧 min*当前数
            min = Math.min(nums[i], Math.min(temp * nums[i], min * nums[i]));

            // 用当前位置结尾的最大乘积更新全局答案
            result = Math.max(result, max);
        }

        // 返回最大乘积子数组的乘积值
        return result;
    }
}

java

🎯 举例详解#

让我们用一个完整的例子来看代码是如何工作的：

nums = [2,-3,-4]

第一步：初始化
max = 2, min = 2, result = 2

第二步：处理 -3
temp = 2
新max = max(-3, max(2×(-3), 2×(-3))) = -3
新min = min(-3, min(2×(-3), 2×(-3))) = -6
result = max(2, -3) = 2

第三步：处理 -4
temp = -3
新max = max(-4, max(-3×(-4), -6×(-4))) = 24
新min = min(-4, min(-3×(-4), -6×(-4))) = -4
result = max(2, 24) = 24

plaintext

💡 小技巧#

遇到负数别怕，想想负负得正
用临时变量保存之前的最大值
别忘了单个数字也是一种选择

🎓 面试时这么说#

如果面试遇到这题，建议这样展开思路：

先说明这题的特别之处：负数的存在使得最大值可能来自之前的最小值
用简单例子说明为什么需要同时维护最大值和最小值
解释动态规划的状态定义和转移过程
最后提到空间优化：只需要保存前一个状态

🔍 相似题目#

最大子数组和（没有负数乘法的情况）
环形数组的最大和（思路类似）

记住，解决动态规划问题的关键是找到正确的状态定义。在这道题中，因为负数的存在，我们需要同时记录最大值和最小值。希望这篇文章能帮助你更好地理解这个问题！