乘积最大子数组——同时维护最大最小值的双DP技巧

老张2026/4/30大约 6 分钟

乘积最大子数组——同时维护最大最小值的双DP技巧

适读人群：Java后端工程师、线性DP进阶学习者 | 阅读时长：约18分钟 | 难度：Medium

开篇故事

乘积最大子数组是最大子数组和（Kadane算法）的"乘法版"，但难度高了不少。

原因在于负数的存在：两个负数相乘得正数，一个之前很小的负数乘以当前的负数，可能瞬间变成最大值。所以单纯维护"以当前位置结尾的最大乘积"是不够的，还需要同时维护"以当前位置结尾的最小乘积"（负数越小，乘以负数后越大）。

这个"同时维护最大和最小"的双DP技巧，是这道题的核心创新点，也是面试中非常容易考到的思维点。第一次见到这种思路往往会觉得"为什么要维护最小？"，理解之后会觉得非常优雅。

一、题目解析

题号：LeetCode 152. Maximum Product Subarray

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

示例：

输入：nums = [2,3,-2,4]，输出：6（子数组 [2,3]）
输入：nums = [-2,0,-1]，输出：0（子数组 [0]）

二、DP思路推导

2.1 为什么需要同时维护最大和最小

对比最大子数组和（Kadane算法）：

maxSum[i] = max(nums[i], maxSum[i-1] + nums[i])

对于乘积，直接类比会失效：

maxProd[i] = max(nums[i], maxProd[i-1] * nums[i])  // 错误！

反例：nums = [-2, 3, -4]

maxProd = [-2, 3, max(3×(-4), -4)] = [-2, 3, -4]，答案是3
但实际最大乘积是 (-2)×3×(-4) = 24！

原因：当 nums[i] 为负数时，前面的"最大值"乘以负数变成最小，前面的"最小值"乘以负数反而变成最大。

因此必须同时维护以 i 结尾的最大乘积（maxProd）和最小乘积（minProd）。

2.2 状态定义

maxProd[i] = 以 nums[i] 结尾的子数组中，乘积的最大值

minProd[i] = 以 nums[i] 结尾的子数组中，乘积的最小值

2.3 状态转移方程

对于每个位置 i，有三种选择：

只包含 nums[i] 本身（重新开始）
在前面的最大乘积基础上乘以 nums[i]（nums[i]正时扩大最大，负时需要考虑）
在前面的最小乘积基础上乘以 nums[i]（nums[i]负时使最小变成最大）

maxProd[i] = max(nums[i], maxProd[i-1] * nums[i], minProd[i-1] * nums[i])
minProd[i] = min(nums[i], maxProd[i-1] * nums[i], minProd[i-1] * nums[i])

理解关键：

当 nums[i] > 0：max乘正数还是max，min乘正数还是min（正常情况）
当 nums[i] < 0：max乘负数变成min，min乘负数变成max（翻转！）
当 nums[i] = 0：乘积重置为0

把三者取最大和最小，一个公式统一处理所有情况。

2.4 状态转移示意

nums = [-2, 3, -4]

初始：maxProd[-1]=1, minProd[-1]=1 (或直接从i=0开始初始化)

i=0, nums=-2:
  maxProd[0] = max(-2, 1×(-2), 1×(-2)) = -2
  minProd[0] = min(-2, ...) = -2

i=1, nums=3:
  maxProd[1] = max(3, (-2)×3, (-2)×3) = max(3, -6, -6) = 3
  minProd[1] = min(3, -6, -6) = -6

i=2, nums=-4:
  maxProd[2] = max(-4, 3×(-4), (-6)×(-4)) = max(-4, -12, 24) = 24
  minProd[2] = min(-4, -12, 24) = -12

最大乘积 = max(maxProd[0], maxProd[1], maxProd[2]) = max(-2, 3, 24) = 24 ✓

三、解法一：双DP（空间O(n)）

public class MaximumProductSubarray {
    
    /**
     * 152. 乘积最大子数组 - 双DP
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] maxProd = new int[n];  // 以nums[i]结尾的最大乘积
        int[] minProd = new int[n];  // 以nums[i]结尾的最小乘积
        
        maxProd[0] = nums[0];
        minProd[0] = nums[0];
        int result = nums[0];
        
        for (int i = 1; i < n; i++) {
            // 三种选择取最大/最小
            maxProd[i] = Math.max(nums[i],
                         Math.max(maxProd[i - 1] * nums[i], minProd[i - 1] * nums[i]));
            minProd[i] = Math.min(nums[i],
                         Math.min(maxProd[i - 1] * nums[i], minProd[i - 1] * nums[i]));
            result = Math.max(result, maxProd[i]);
        }
        
        return result;
    }
}

Mermaid状态转移图：

四、解法二：空间优化（O(1)）

由于只依赖前一个位置，用变量替代数组：

/**
 * 152. 乘积最大子数组 - 空间优化
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
public int maxProductOptimized(int[] nums) {
    int maxProd = nums[0];
    int minProd = nums[0];
    int result = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
        int prevMax = maxProd;
        int prevMin = minProd;
        maxProd = Math.max(nums[i], Math.max(prevMax * nums[i], prevMin * nums[i]));
        minProd = Math.min(nums[i], Math.min(prevMax * nums[i], prevMin * nums[i]));
        result = Math.max(result, maxProd);
    }
    
    return result;
}

注意：必须先保存 prevMax 和 prevMin，再更新 maxProd 和 minProd。否则计算 minProd 时用的是已更新的 maxProd，会出错。

五、特殊情况分析

数组包含0的情况：

当 nums[i] = 0 时：

maxProd = max(0, 0, 0) = 0
minProd = 0

0相当于"重置"，之后的子数组重新从0开始积累。这是正确的，因为包含0的子数组乘积必然为0，最大值只能从0之后重新开始。

全负数的情况：

nums = [-2, -3, -4]，偶数个负数乘积为正。

i=0: max=-2, min=-2
i=1: max=max(-3, -2×-3=-6×...) → max=6, min=-6...

等等，让我重算：

i=1: max=max(-3, (-2)×(-3)=6, (-2)×(-3)=6) = 6, min=min(-3, 6, 6)=-3
i=2: max=max(-4, 6×(-4)=-24, (-3)×(-4)=12) = 12, min=min(-4, -24, 12) = -24

答案12（-3×-4=12）。正确！

六、举一反三

LeetCode 53. 最大子数组和（Kadane）：乘积版的前身，只维护一个max
LeetCode 713. 乘积小于K的子数组：滑动窗口
LeetCode 2708. 一个小组的最大实力值：乘积类的扩展

七、踩坑实录

坑一：计算minProd时用了已更新的maxProd

在O(1)版本里，必须先保存 prevMax 和 prevMin，再计算新的 maxProd 和 minProd。如果先更新 maxProd 再算 minProd，minProd 用的是错误的"新 maxProd"。

坑二：只考虑了正数情况，忘了负负得正

很多人只维护了maxProd，遇到负负得正就算错了。双DP的核心就是同时维护min，这是这道题与最大子数组和最本质的区别。

坑三：result初始化为0

如果所有数都是负数，最大乘积也是负数（比如只有一个元素-1时答案是-1），如果result初始化为0就会错误地返回0。应该初始化为nums[0]。

八、总结

乘积最大子数组的核心：

双DP技巧：同时维护最大值和最小值，因为负数相乘会导致最大最小互换。

maxProd[i] = max(nums[i], maxProd[i-1]*nums[i], minProd[i-1]*nums[i])
minProd[i] = min(nums[i], maxProd[i-1]*nums[i], minProd[i-1]*nums[i])

这个模式在其他需要"同时考虑极值"的DP题中也会出现，遇到乘法类、可正可负的连续子数组问题，第一反应就是考虑双DP。