152. 乘积最大子数组

力扣题目链接 (opens new window)

题目描述

给你一个整数数组 nums,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

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

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

• 1 <= nums.length <= 2 * 10⁴
• -10 <= nums[i] <= 10
• nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

思路

这道题和 53. 最大子数组和 很像,但有一个关键区别:乘法中负数×负数会变成正数。

为什么不能直接套用最大子数组和的思路?

在最大子数组和中,如果前面的和是负数,直接舍弃就行。但在乘积问题中,当前的最小值(负数)乘以下一个负数,可能变成最大值。

例如 [-2,3,-4]:

• 到 -2 时,最大乘积 = -2
• 到 3 时,最大乘积 = 3
• 到 -4 时,如果只记录最大值,会算成 3×(-4)=-12
• 但其实 -2×3×(-4)=24 才是最大的!

所以需要同时维护当前的最大乘积和最小乘积。

动态规划思路

定义两个 DP 数组:

• dpMax[i]:以 nums[i] 结尾的子数组的最大乘积
• dpMin[i]:以 nums[i] 结尾的子数组的最小乘积

递推公式:

到达 nums[i] 时,有三种选择:

1. nums[i] 单独作为子数组
2. dpMax[i-1] * nums[i](前面的最大值继续乘)
3. dpMin[i-1] * nums[i](前面的最小值继续乘,可能翻身)

所以:

• dpMax[i] = max(nums[i], dpMax[i-1] * nums[i], dpMin[i-1] * nums[i])
• dpMin[i] = min(nums[i], dpMax[i-1] * nums[i], dpMin[i-1] * nums[i])

为什么 dpMin 也要考虑 dpMax?

因为 nums[i] 可能是负数,dpMax[i-1] 是正数,乘起来变成负数,可能是新的最小值。

最终答案是所有 dpMax[i] 中的最大值。

空间优化

因为 dpMax[i] 和 dpMin[i] 只依赖前一个位置,可以用两个变量滚动更新,空间优化到 O(1)。

模拟过程

以 nums = [2,3,-2,4] 为例:

i	nums[i]	dpMax 计算	dpMax[i]	dpMin 计算	dpMin[i]	result
0	2	2	2	2	2	2
1	3	max(3, 2×3, 2×3)	6	min(3, 2×3, 2×3)	3	6
2	-2	max(-2, 6×(-2), 3×(-2))	-2	min(-2, 6×(-2), 3×(-2))	-12	6
3	4	max(4, (-2)×4, (-12)×4)	4	min(4, (-2)×4, (-12)×4)	-48	6

最终答案是 6。

再看 nums = [-2,3,-4]:

i	nums[i]	dpMax 计算	dpMax[i]	dpMin 计算	dpMin[i]	result
0	-2	-2	-2	-2	-2	-2
1	3	max(3, (-2)×3, (-2)×3)	3	min(3, (-2)×3, (-2)×3)	-6	3
2	-4	max(-4, 3×(-4), (-6)×(-4))	24	min(-4, 3×(-4), (-6)×(-4))	-12	24

看到了吗?dpMin[1] = -6 乘以 nums[2] = -4,负负得正,变成了最大值 24!

drawio 提示词: 画两张图展示 DP 过程。第一张用数组 [2,3,-2,4] 展示正常情况,画出 dpMax 和 dpMin 两条折线,标注关键转折点。第二张用数组 [-2,3,-4] 展示负数翻身,重点标注 dpMin=-6 遇到 nums[i]=-4 后,变成 dpMax=24 的过程,用箭头和计算公式说明"负×负=正"的关键。两张图画布统一,Logo 放左下角。

文件名:

• 0152.maximum-product-subarray-01-normal-case.drawio
• 0152.maximum-product-subarray-02-negative-flip.drawio

解题代码

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int result = nums[0];
        int dpMax = nums[0]; // 以当前元素结尾的最大乘积
        int dpMin = nums[0]; // 以当前元素结尾的最小乘积
        
        for (int i = 1; i < nums.size(); i++) {
            int prevMax = dpMax;
            int prevMin = dpMin;
            
            // 更新 dpMax 和 dpMin,要同时考虑前面的最大值和最小值
            dpMax = max({nums[i], prevMax * nums[i], prevMin * nums[i]});
            dpMin = min({nums[i], prevMax * nums[i], prevMin * nums[i]});
            
            result = max(result, dpMax);
        }
        
        return result;
    }
};

复杂度分析

• 时间复杂度:O(n),遍历一遍数组
• 空间复杂度:O(1),只用了常数个变量

其他语言

Python3

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        result = dpMax = dpMin = nums[0]
        
        for i in range(1, len(nums)):
            prevMax, prevMin = dpMax, dpMin
            
            dpMax = max(nums[i], prevMax * nums[i], prevMin * nums[i])
            dpMin = min(nums[i], prevMax * nums[i], prevMin * nums[i])
            
            result = max(result, dpMax)
        
        return result

Java

class Solution {
    public int maxProduct(int[] nums) {
        int result = nums[0];
        int dpMax = nums[0];
        int dpMin = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            int prevMax = dpMax;
            int prevMin = dpMin;
            
            dpMax = Math.max(nums[i], Math.max(prevMax * nums[i], prevMin * nums[i]));
            dpMin = Math.min(nums[i], Math.min(prevMax * nums[i], prevMin * nums[i]));
            
            result = Math.max(result, dpMax);
        }
        
        return result;
    }
}

Go

func maxProduct(nums []int) int {
    result := nums[0]
    dpMax := nums[0]
    dpMin := nums[0]
    
    for i := 1; i < len(nums); i++ {
        prevMax := dpMax
        prevMin := dpMin
        
        dpMax = max(nums[i], max(prevMax * nums[i], prevMin * nums[i]))
        dpMin = min(nums[i], min(prevMax * nums[i], prevMin * nums[i]))
        
        result = max(result, dpMax)
    }
    
    return result
}

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

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

JavaScript

var maxProduct = function(nums) {
    let result = nums[0];
    let dpMax = nums[0];
    let dpMin = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        const prevMax = dpMax;
        const prevMin = dpMin;
        
        dpMax = Math.max(nums[i], prevMax * nums[i], prevMin * nums[i]);
        dpMin = Math.min(nums[i], prevMax * nums[i], prevMin * nums[i]);
        
        result = Math.max(result, dpMax);
    }
    
    return result;
};

与代码随想录联系

这道题和代码随想录中的 53. 最大子数组和 是经典的对比题。

两者的核心区别:

• 最大子数组和:加法问题,负数只会让和变小,所以只需维护一个"最大和"
• 乘积最大子数组:乘法问题,负数×负数会变大,所以需要同时维护"最大乘积"和"最小乘积"

这道题告诉我们一个重要的 DP 技巧:当问题中存在"负负得正"这种反转情况时,要同时维护最优和最差两个状态。

类似的思想在其他题目中也会出现,比如股票买卖问题中,可能需要同时维护"持有股票"和"不持有股票"两种状态。

建议录友们把这道题和 53 题对比着看,理解 DP 中"状态维护"的灵活性。