乘积最大子数组：负负得正的动态规划妙用

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

🤔 问题是什么？

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

比如：

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

🌟 为什么这题很特别？

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

nums = [1,2,3,4]

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

但如果数组包含负数呢？

nums = [2,-3,4]

这时情况就变得有趣了：

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

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

再看一个更有趣的例子：

nums = [2,-3,-4]

这时因为负负得正：

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

所以答案是 12！

💡 关键发现：负负得正！

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

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

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

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

🎨 动态规划方案

让我们定义：

• 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

📝 代码实现

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

class Solution {
    public int maxProduct(int[] nums) {
        // 至少会有一个数
        if (nums == null || nums.length == 0) return 0;
        
        // 初始化：第一个数既是最大值也是最小值
        int max = nums[0];
        int min = nums[0];
        // 记录全局最大值
        int result = nums[0];
        
        // 从第二个数开始遍历
        for (int i = 1; i < nums.length; i++) {
            // 临时保存上一个最大值，因为计算最小值时会用到
            int temp = max;
            
            // 计算当前位置的最大值
            // 可能是：当前数、前面最大值×当前数、前面最小值×当前数
            max = Math.max(nums[i], Math.max(max * nums[i], min * nums[i]));
            
            // 计算当前位置的最小值
            min = Math.min(nums[i], Math.min(temp * nums[i], min * nums[i]));
            
            // 更新全局最大值
            result = Math.max(result, max);
        }
        
        return result;
    }
}

🎯 举例详解

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

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

💡 小技巧

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

🎓 面试时这么说

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

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

🔍 相似题目

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

---

作者：忍者算法
公众号：忍者算法

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

#算法面试 #LeetCode #动态规划 #最大子数组