152. 乘积最大子数组——maximum-product-subarray

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

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

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

示例 1:

1
2
3

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

示例 2:

1
2
3

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

提示:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• nums 的任何子数组的乘积都 保证 是一个 32-位 整数

我的答案333ms|击败6.74%

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int curr = nums[i];
            for (int j = i+1; j < nums.length; j++) {
                max = Math.max(max, curr);
                curr *= nums[j];
            }
            max = Math.max(max, curr);
        }
        return max;
    }
}

方法一：动态规划

• 关键：维护上一个状态

思路和算法

如果我们用 fmax(i) 开表示以第 i 个元素结尾的乘积最大子数组的乘积，a 表示输入参数 nums，那么根据「53. 最大子序和」的经验，我们很容易推导出这样的状态转移方程：

$f_{\text{max}}(i) = \max\limits_{i=1}^{n} \left{ f_{}(i-1) \times a_i,\ a_i \right}$

它表示以第 i 个元素结尾的乘积最大子数组的乘积可以考虑 a**i 加入前面的 fmax(i−1) 对应的一段，或者单独成为一段，这里两种情况下取最大值。求出所有的 fmax(i) 之后选取最大的一个作为答案。

可是在这里，这样做是错误的。为什么呢？

因为这里的定义并不满足「最优子结构」。具体地讲，如果 a={5,6,−3,4,−3}，那么此时 fmax 对应的序列是 {5,30,−3,4,−3}，按照前面的算法我们可以得到答案为 30，即前两个数的乘积，而实际上答案应该是全体数字的乘积。我们来想一想问题出在哪里呢？问题出在最后一个 −3 所对应的 fmax 的值既不是 −3，也不是 4×−3，而是 5×30×(−3)×4×(−3)。所以我们得到了一个结论：当前位置的最优解未必是由前一个位置的最优解转移得到的。

我们可以根据正负性进行分类讨论。

考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。于是这里我们可以再维护一个 fmin(i)，它表示以第 i 个元素结尾的乘积最小子数组的乘积，那么我们可以得到这样的动态规划转移方程：

$f_{\text{max}}(i) = \max\limits_{i=1}^{n} \left{ f_{\text{max}}(i-1) \times a_i,\ f_{\text{min}}(i-1) \times a_i,\ a_i \right}$

$f_{\text{min}}(i) = \min\limits_{i=1}^{n} \left{ f_{\text{max}}(i-1) \times a_i,\ f_{\text{min}}(i-1) \times a_i,\ a_i \right}$

它代表第 i 个元素结尾的乘积最大子数组的乘积 fmax(i)，可以考虑把 ai 加入第 i−1 个元素结尾的乘积最大或最小的子数组的乘积中，二者加上 ai*，三者取大，就是第 *i 个元素结尾的乘积最大子数组的乘积。第 i 个元素结尾的乘积最小子数组的乘积 fmin(i) 同理。

不难给出这样的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int maxProduct(int[] nums) {
        int length = nums.length;
        long[] maxF = new long[length];
        long[] minF = new long[length];
        for (int i = 0; i < length; i++) {
            maxF[i] = nums[i];
            minF[i] = nums[i];
        }
        for (int i = 1; i < length; ++i) {
            maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
            if (minF[i] < (-1 << 31)) {
                minF[i] = nums[i];
            }
        }
        int ans = (int) maxF[0];
        for (int i = 1; i < length; ++i) {
            ans = Math.max(ans, (int) maxF[i]);
        }
        return ans;
    }
}

易得这里的渐进时间复杂度和渐进空间复杂度都是 O(n)。

详细解答

一、先解决核心困惑：为什么不能照搬「最大子序和」？

「最大子序和」的状态转移是 f(i) = max(f(i-1)+a[i], a[i])，核心逻辑是：加了当前元素后，要么比之前更大，要么单独开一段。

但这个逻辑在「乘积」里完全不成立 —— 因为乘积有个特殊属性：负负得正。

举个例子（题目里的 [5,6,-3,4,-3]）：

• 按「最大子序和」思路，maxF 会是 [5, 30, -3, 4, -3]，最大是 30；
• 但实际最优解是全体乘积：5×6×(-3)×4×(-3) = 1080，比 30 大得多！

问题出在哪？

当当前元素是负数（比如最后一个 -3）时，前一个位置的「最小乘积」（比如 -3×4 = -12）乘以当前负数，会变成正数 (-12)×(-3)=36，再往前连乘还能更大。

而「最大子序和」的思路只关注前一个的「最大值」，完全忽略了「最小值 × 负数 = 更大值」的情况 —— 这就是「最优子结构」不成立的原因。

二、关键突破：为什么要维护「最小乘积子数组」minF？

我们需要分情况讨论「当前元素是正数 / 负数」，才能找到以当前元素结尾的最大乘积：

所以，我们不能只存「最大乘积」maxF，必须额外存「最小乘积」minF—— 它的作用就是「为当前负数元素，提供一个 “负负得正” 的机会」。

三、状态转移方程拆解（最核心的部分）

我们定义：

• maxF[i]：以第 i 个元素结尾的「乘积最大子数组」的乘积；
• minF[i]：以第 i 个元素结尾的「乘积最小子数组」的乘积。

要得到 maxF[i] 和 minF[i]，每个位置都有 3 种选择，必须全部考虑到：

1. 只选当前元素 nums[i]（前面的子数组乘积是负数 / 0，不如单独开一段）；
2. 当前元素 × 前一个的最大乘积 maxF[i-1]×nums[i]（当前为正，乘前面的大值）；
3. 当前元素 × 前一个的最小乘积 minF[i-1]×nums[i]（当前为负，乘前面的小值，负负得正）。

所以状态转移方程就是：

• maxF[i] = max( 选当前元素, 前max * 当前, 前min * 当前 )
• minF[i] = min( 选当前元素, 前max * 当前, 前min * 当前 )

举个具体例子（nums = [5,6,-3,4,-3]），一步步算：

最终 maxF 数组是 [5,30,-3,4,1080]，最大值 1080—— 和正确答案一致！

四、代码逐行解释（解决细节困惑）

现在看代码，每一行都能对应上面的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public int maxProduct(int[] nums) {
        int length = nums.length;
        // 1. 为什么用long数组？
        // 因为int的范围是[-2^31, 2^31-1]，乘积容易溢出（比如两个大正数相乘超2^31-1）
        // 用long存，最后转int，避免溢出导致的错误
        long[] maxF = new long[length];
        long[] minF = new long[length];
        
        // 2. 初始化：每个元素单独作为子数组时，最大和最小乘积都是自己
        for (int i = 0; i < length; i++) {
            maxF[i] = nums[i];
            minF[i] = nums[i];
        }
        
        // 3. 遍历计算maxF和minF（从第1个元素开始，因为第0个已经初始化）
        for (int i = 1; i < length; ++i) {
            // 状态转移：三者取最大（当前元素、前max×当前、前min×当前）
            maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
            // 状态转移：三者取最小（同理，覆盖所有情况）
            minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
            
            // 4. 溢出处理：如果minF[i]溢出成极小的负数（比如超long范围？其实long很难溢出，但保险）
            // 此时直接取nums[i]（因为溢出的极小值已经没有意义，不如单独取当前元素）
            if (minF[i] < (-1 << 31)) {
                minF[i] = nums[i];
            }
        }
        
        // 5. 找maxF数组中的最大值，就是答案
        int ans = (int) maxF[0];
        for (int i = 1; i < length; ++i) {
            ans = Math.max(ans, (int) maxF[i]);
        }
        return ans;
    }
}

关键细节补充：

• 为什么用long？比如 nums = [2,3,-2,4, ...] 后面如果再乘几个大数，int 会装不下（比如 2×3×(-2)×(-4)×... 乘积超 2^31-1），用long能避免溢出错误；
• 溢出处理那行是 “保险操作”：(-1 << 31) 是 int 的最小值（-2147483648），如果minF[i]比这个还小，说明溢出了（long 理论上不会，但极端情况可能），此时直接取nums[i]更合理；
• 初始化时maxF[i] = minF[i] = nums[i]：因为单个元素的子数组，最大和最小乘积都是它自己（没有其他选择）。