本文概览：本文讲解乘积最大子数组的核心思路：dp[i] 表示以 nums[i] 结尾的最大乘积，但负数会让最大变最小，必须同时维护以 nums[i] 结尾的最大和最小乘积，O(n) 一次遍历

一、题目

乘积最大子数组 题目图片

二、题目分析

1. 题目要求

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

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

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

示例 1：nums = [2, 3, -2, 4] → 6（[2, 3]）

示例 2：nums = [-2, 0, -1] → 0（[-2, -1] 不是连续子数组，所以不能算）

2. 暴力思路的问题

最直觉的做法：枚举所有连续子数组，逐个算乘积取最大。最外层枚举子数组的长度（1 到 n），内层枚举该长度下所有合法的起点，最内层把这一段从头累乘到尾——三层 for 嵌套，O(n³)。

而且里面有大量重复计算：算长度为 3 的子数组乘积时，长度为 2 的那段早就算过一遍了，又被推倒重算。比如 nums = [2,3,-2,4]：

1
2
3
4
长度 1:  2,    3,    -2,   4
长度 2:  6,   -6,    -8
长度 3:  -12,  -24
长度 4:  -48

长度 3 的 -12 = 2×3×-2，其中 2×3 的乘积 6 在算长度 2 时已经算出来了，却被扔掉重算。

怎么避免重复？ 从前往后遍历，每来一个新元素，新增的子数组只有"以这个新元素结尾的那些"。比如从 [2,3] 走到 [2,3,-2]：

1
新增的子数组:  [-2], [3,-2], [2,3,-2]

每个新子数组的乘积 = 新元素 × 某个"以新元素前一个位置结尾的子数组的乘积"。只要把以每个位置结尾的子数组乘积存下来，新增的全部 O(1) 算出来。

大问题拆成同形式的小问题 + 前面怎么拼的不影响后面使用（无后效性）——动态规划的味道出来了。

3. 需要解决哪几个问题？

问题一：状态怎么定义？——以 nums[i] 结尾，要记录多少个子数组的乘积？

问题二：转移方程怎么写？——已知前面的记录，怎么推出以 nums[i] 结尾的乘积？

问题三：负数带来的麻烦怎么处理？——负负得正，乘一个负数会让最大变最小、最小变最大，只记最大值够吗？

三、方法一：DP 数组记录以每个位置结尾的所有乘积，O(n²)

1. 思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxProduct(int[] nums) {
        int[] dp = new int[nums.length + 1];
        dp[0] = 1;
        dp[1] = nums[0];
        int size = 1;
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            for (int j = size; j > 0; j--) {
                dp[j+1] = dp[j] * nums[i];
                max = Math.max(max, dp[j+1]);
            }
            size++;
            dp[1] = nums[i];
        }
        return max;
    }
}

思路简要说明：

  1. 状态定义：dp[k] 表示以当前位置结尾、长度为 k 的子数组的乘积
  2. 转移方程：新元素来了，dp新[k+1] = dp旧[k] × nums[i]（以 i-1 结尾长度 k 的子数组接上 nums[i]）
  3. 更新顺序从后往前：防覆盖（详解见后）
  4. **时间复杂度 O(n²)**，空间 O(n)

2. 思路详解

第一步：解决状态定义——怎么把"以每个位置结尾的乘积"装进数组？

题目分析的结论是"把以每个位置结尾的子数组乘积存下来"。但一个位置的结尾不止一个子数组——以索引 2 结尾的可以是 [−2]、[3,−2]、[2,3,−2]，长度 1 到 3 都有。所以要记的不止一个数，得按长度开一格：

dp[k] = 以当前位置结尾、长度为 k 的子数组的乘积。

dp[0] = 1 是哨兵：长度 0 的子数组乘积定义为 1（空乘），它让 dp[1] = dp[0] × nums[i] 也能走统一的转移公式。

第二步：解决转移方程——新元素来了怎么整体更新？

遍历到 nums[i] 时，以 i 结尾的每个子数组，都等于"某个以 i-1 结尾的子数组 × nums[i]"：

1
2
3
长度 2 的以 i 结尾  = 长度 1 的以 i-1 结尾 × nums[i]   → dp新[2] = dp旧[1] × nums[i]
长度 3 的以 i 结尾  = 长度 2 的以 i-1 结尾 × nums[i]   → dp新[3] = dp旧[2] × nums[i]
...以此类推

统一写：dp新[k+1] = dp旧[k] × nums[i]。全部乘完后，再补上长度 1 的：dp[1] = nums[i]。

第三步：为什么要从后往前更新？

转移公式是 dp[j+1] = dp[j] × nums[i]——**新值依赖同一轮还没被更新的旧 dp[j]**。

如果从前往后：先算 dp[2] = dp[1] × nums[i]，此时 dp[1] 还是旧的，对；接着算 dp[3] = dp[2] × nums[i]，但 dp[2] 已经被第一步覆盖成新值了——相当于 nums[i] 乘了两次，错。

从后往前就没事：先算 dp[4] = dp[3] × nums[i]（dp[3] 还是旧的），再算 dp[3] = dp[2] × nums[i]（dp[2] 还是旧的）……每个值被读的时候都还没被写，全对。这就是内层 for (int j = size; j > 0; j--) 倒着走的原因。

第四步：完整执行过程

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

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
初始：dp = [1, 2], size=1, max=2
      dp[1]=2 表示以索引0结尾、长度1的子数组 [2]

i=1 (num=3)：
  max = max(2, 3) = 3          ← 长度1的 [3] 先参与比较
  j=1: dp[2] = dp[1] * 3 = 6   ← [2,3]，max = 6
  size=2, dp[1] = 3            ← [3]
  dp = [1, 3, 6]
      dp[1]=3 ([3])，dp[2]=6 ([2,3])

i=2 (num=-2)：
  max = max(6, -2) = 6
  j=2: dp[3] = dp[2] * (-2) = -12   ← [2,3,-2]
  j=1: dp[2] = dp[1] * (-2) = -6    ← [3,-2]
  size=3, dp[1] = -2                ← [-2]
  dp = [1, -2, -6, -12]
  max 仍是 6

i=3 (num=4)：
  max = max(6, 4) = 6
  j=3: dp[4] = dp[3] * 4 = -48   ← [2,3,-2,4]
  j=2: dp[3] = dp[2] * 4 = -24   ← [3,-2,4]
  j=1: dp[2] = dp[1] * 4 = -8    ← [-2,4]
  size=4, dp[1] = 4              ← [4]
  dp = [1, 4, -8, -24, -48]
  max 仍是 6

返回 max = 6 ✓（对应 [2,3]）

每一步 dp 数组就是"以当前遍历位置结尾的所有子数组的乘积表"，max 在每个新乘积诞生时顺手比较。

3. 复杂度分析

**时间复杂度 O(n²)**：外层 n 个元素，内层每次最多更新 i 个长度。

**空间复杂度 O(n)**：dp 数组。

对比暴力的 O(n³)，省掉的是"同一段前缀被反复累乘"；但每来一个元素还是要扫一遍整串 dp——方法二将继续砍这里。

四、引导思考：方法一还能优化吗？

方法一每来一个新元素，都要把整串 dp 从后往前乘一遍更新——O(n²)。这里面还有没有没必要的计算？

看看每轮更新出来的这一串新乘积：它们是"以 i 结尾"的所有子数组乘积，一大串。但往后看，下一轮 (i+1) 要用它们乘 nums[i+1] 的时候，真正能影响最终答案的只有两个值：这串乘积里的最大值和最小值。

为什么？往后接元素想让乘积变大，只有两种情况：

1
2
前一个位置结尾的最大乘积（正数）× 正的新元素   → 越乘越大
前一个位置结尾的最小乘积（负数）× 负的新元素   → 负负得正，翻身变大

也就是说，新的最大值可能从"接前一个最大"来，也可能从"接前一个最小"来——只记最大值，第二条路就断了。

用 nums = [3, -2, -3, 5] 验证一下只记最大值会错在哪：

1
2
3
4
i=0: 最大 = 3
i=1: 最大 = max(-2, 3*-2) = -2        ← 以 -2 结尾的最小乘积 -6 被丢了
i=2: 最大 = max(-3, -2*-3) = 6        ← 只接了前一个最大 -2
i=3: 最大 = max(5, 6*5) = 30

但真正的最大乘积是 90：

1
2
[3, -2, -3]      = 18    ← 3×-2 = -6（i=1 的最小乘积），-6 × -3 = 18 翻身
[3, -2, -3, 5]   = 90    ← 18 × 5 接上新元素

i=1 时如果保留最小乘积 -6，i=2 就有 -6 × -3 = 18 这一支，i=3 再接 5 得 90。只记最大值把 -6 丢了，18 和 90 全部漏掉。

结论：这串新乘积里的中间部分全是无效计算，只需要同时维护两个值——以当前位置结尾的最大乘积和最小乘积。每来一个新元素，两个值各 O(1) 更新，复杂度直接降到 O(n)。

五、方法二：只维护最大和最小两个值，O(n)

1. 思路概览

1
2
3
4
5
6
7
8
9
10
11
12
public int maxProduct(int[] nums) {
    int curMax = nums[0];
    int curMin = nums[0];
    int global = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int tempMax = curMax;
        curMax = Math.max(nums[i], Math.max(tempMax * nums[i], curMin * nums[i]));
        curMin = Math.min(nums[i], Math.min(tempMax * nums[i], curMin * nums[i]));
        global = Math.max(curMax, global);
    }
    return global;
}

思路简要说明：

  1. 状态定义：curMax / curMin 表示以 nums[i] 结尾的最大/最小乘积，global 记录全局答案
  2. 转移方程：三个候选取极值——单独 nums[i]、接前一个最大、接前一个最小
  3. **时间复杂度 O(n)**，空间 O(1)

2. 思路详解

第一步：解决状态定义——三个变量各管什么？

引导思考的结论：只需要"以当前位置结尾的最大乘积"和"最小乘积"两个值。所以：

  • curMax = 以 nums[i] 结尾的最大乘积
  • curMin = 以 nums[i] 结尾的最小乘积

那 global 是干什么的？答案不一定以最后一个元素结尾。比如 nums = [2, 0, 1]，最大乘积是 2（以索引 0 结尾），而遍历到末尾时 curMax 是 1。所以要用 global 把每个位置的 curMax 都收一遍，最后返回 global——和方法一里 max 的角色完全一样。

第二步：解决转移方程——curMax 和 curMin 怎么更新？

以 nums[i] 结尾的子数组只有两类：

  • 只包含自己：nums[i]（新起一段）
  • 接着前面的：nums[i] ×（以 nums[i-1] 结尾的某个子数组乘积）

第二类里，能接出最大值的是前一个 curMax（正数接正数涨）或前一个 curMin（负数接负数翻身）；能接出最小值的同理。所以两个更新公式都是三个候选取极值：

1
2
3
4
5
6
7
curMax = max(nums[i],              // 单独成段
             tempMax * nums[i],     // 接前一个最大
             curMin * nums[i])      // 接前一个最小（可能翻身变正）

curMin = min(nums[i],              // 单独成段
             tempMax * nums[i],     // 接前一个最大
             curMin * nums[i])      // 接前一个最小

tempMax 是干什么的？ curMax 先被更新，curMin 后更新，但 curMin 的公式里要用更新前的 curMax。如果不暂存，curMin 那行用的就是新 curMax，状态用错。所以先用 int tempMax = curMax 把旧值存下来——和方法一"从后往前更新防覆盖"是同一个问题的两种解法：**都是"新值依赖旧值，别让旧值提前被覆盖"**。

第三步：完整执行过程（示例 1）

nums = [2, 3, -2, 4]，答案是 6（[2, 3]）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
初始：curMax=2, curMin=2, global=2

i=1 (num=3)：
  tempMax = 2
  curMax = max(3, 2*3, 2*3) = 6           ← 接前一个最大 2 涨到 6
  curMin = min(3, 2*3, 2*3) = 3           ← 单独 3 是当前最小
  global = max(6, 2) = 6

i=2 (num=-2)：
  tempMax = 6
  curMax = max(-2, 6*-2, 3*-2) = -2       ← 单独 -2 最大，6*-2=-12, 3*-2=-6
  curMin = min(-2, 6*-2, 3*-2) = -12      ← 接前一个最大 6 跌到 -12
  global = max(-2, 6) = 6                  ← 答案仍是 6

i=3 (num=4)：
  tempMax = -2
  curMax = max(4, -2*4, -12*4) = 4        ← 单独 4 最大
  curMin = min(4, -2*4, -12*4) = -48      ← 接最小 -12 跌到 -48
  global = max(4, 6) = 6                   ← 答案仍是 6 ✓

注意 i=2 的 curMin = -12：这是"被负数翻正的历史"。如果下一轮来一个负数，curMin × 负数就会翻成正，变成新一轮的 curMax——这正是必须保留 curMin 的原因。

对照方法一同一时刻的 dp 数组 [1, -2, -6, -12]：curMax=-2、curMin=-12 正是那串乘积里的最大和最小，方法二把中间的 -6 直接丢弃了——它既当不了最大也当不了最小，对后续毫无影响。

第四步：示例 2 看 0 的屏障作用

nums = [-2, 0, -1]，答案是 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
初始：curMax=-2, curMin=-2, global=-2

i=1 (num=0)：
  tempMax = -2
  curMax = max(0, -2*0, -2*0) = 0        ← 单独 0 最大
  curMin = min(0, -2*0, -2*0) = 0
  global = max(0, -2) = 0

i=2 (num=-1)：
  tempMax = 0
  curMax = max(-1, 0*-1, 0*-1) = -1
  curMin = min(-1, 0*-1, 0*-1) = -1
  global = max(-1, 0) = 0 ✓

观察：遇到 0 时，curMax 和 curMin 同时归零——0 是切割子数组的天然屏障，怎么乘都是 0，之后的状态相当于被重置。这也解释了 [-2, -1] 为什么不能算：中间隔着 0，这两段连不成一个连续子数组，乘积不是 2。

第五步：代码细节

初始值：curMax、curMin、global 都初始化为 nums[0]——以 nums[0] 结尾的最大/最小乘积就是它自己。

数组长度为 1：循环从 i=1 开始，长度为 1 时不进循环，直接返回 global = nums[0] ✓。

3. 复杂度分析

**时间复杂度 O(n)**：一遍遍历，每个元素常数次比较和乘法。

**空间复杂度 O(1)**：三个变量。

对比方法一 O(n²) → O(n)：把"以 i 结尾的所有子数组乘积"压成最大、最小两个代表值，中间的无效乘积全部不算了。

六、对比：和"最大和子数组"的区别

维度 最大和子数组 最大乘积子数组
状态数 1（curSum） 2（curMax 和 curMin）
为什么多 加法单调：和只会越来越大 乘法不单调：负数会让最大变最小
转移 curSum = max(nums[i], curSum+nums[i]) curMax = max(nums[i], curMax*nums[i], curMin*nums[i])
关键观察 要么新起一段，要么接前一段 要么新起，要么接前一个最大，要么接前一个最小

共同点是"站在 i 往回看，前面的结果直接套"。差别只在：加法不怕历史，乘法要让历史能被翻盘。

七、总结

乘积最大子数组的核心思路：

  1. 状态定义：curMax = 以 nums[i] 结尾的最大乘积，curMin = 以 nums[i] 结尾的最小乘积
  2. 同时维护最大和最小：负数会让最大变最小——这是这题和"最大和"的关键差别
  3. 转移方程：三个候选取极值——单独 nums[i]、接前一个最大、接前一个最小（可能翻身）
  4. tempMax 暂存：算 curMax 时需要更新前的 curMax，否则 curMin 用的是新值会错
  5. global 及时更新：算完 curMax 立刻和 global 比，不能攒到最后

和"最大和子数组"的关系：模板几乎一样（"站在 i 往回看，前面的结果直接套"），只是乘法让"前面的结果"必须记两个值（一对相反数：最大和最小）。理解了这个"成对出现"的必要性，剩下的就是套公式。

进一步的小练习：试着改一下"返回的是最大乘积的子数组本身"——你需要在更新 curMax 时同时记录"产生 curMax 的子数组从哪里开始"。这就把 DP 从"标量"升级到了"路径"，是很多"区间类"问题的通用方法。