企业官网建设流程全解析

先坦白一句，这道题我刷了三遍才算真正吃透。第一遍用暴力枚举，在大数组上直接超时；第二遍想偷懒套“最大子数组和”的转移方程，结果被负数的符号变化狠狠上了一课；第三遍才彻底理解动态规划里为什么要同时维护“最大”和“最小”两个状态。LeetCode 152这个题，表面是求一个连续子数组的乘积最大值，实际考的是你对乘法符号特性的理解深度，以及能不能从“加法场景”平滑迁移到“乘法场景”。本文我用Java把常见的几种解法全部拆开揉碎讲一遍，重点推导动态规划的状态定义和转移方程，再附上踩坑记录。无论你是刚接触动态规划的新手，还是准备面试想系统过一遍经典题型的同学，这篇都值得收藏。

1. 题目拆解：乘积最大子数组到底在考什么

1.1 先读懂题意：连续、非空、乘积最大

题目本身很短：给定一个整数数组 nums，找出一个连续子数组，使得该子数组的乘积最大，返回这个最大值。子数组要求连续，并且至少包含一个元素。

举个例子，nums = [2, 3, -2, 4]，所有连续子数组里，[2, 3]的乘积是6，[4]的乘积是4，[2, 3, -2]的乘积是-12，所以最大值是6。注意这里答案不一定是整个数组的乘积，因为负数的存在会让“越长”反而“越小”。

再看一个例子，nums = [-2, 0, -1]，最大乘积是0，而不是2。因为包含0的任意子数组乘积都是0，不包含0的只有[-2]或者[-1]，乘积分别是-2和-1，都不如0大。这个例子说明遇到0时，乘积会“重置”，不能抱着前面的负数不放手。

题目还有个很容易忽略的点：数组元素可以是正数、负数、0，三种情况都要能处理。之前有人问我，如果所有元素都是正数，那最大乘积不就是整个数组的乘积吗？确实如此，但有负数存在后问题就变得有趣了：一个负数是减分项，两个负数却可能变成加分项，这就是这道题和“最大子数组和”最本质的区别。

1.2 暴力法为什么不可行：O(n^2)的时间代价

很多人第一反应就是枚举所有子数组：用两个指针 i 和 j 圈定区间，用一个临时变量累乘区间内所有元素，边乘边更新答案。这种方法逻辑上没有任何问题，代码也简单。

public int maxProductBruteForce(int[] nums) { int max = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { int product = 1; for (int j = i; j < nums.length; j++) { product *= nums[j]; max = Math.max(max, product); } } return max; }

但是，当数组长度达到10万级别时，双重循环要执行约5亿次乘法，实际运行时间会到秒级以上，在在线评测环境里几乎必挂。暴力法作为理解题意的辅助工具是合格的，但绝不是最优解。

也有人会问，能不能用前缀积数组来加速？比如 prefix[i] 表示从开头到第 i 个元素的乘积，然后通过 prefix[j] / prefix[i-1] 计算区间乘积。这个思路在数组全是正数时非常完美，可一旦出现0，除法就会遇到分母为0的问题；退一步说就算用特殊标记处理0，负数区间的乘积符号和大小也不能靠简单的除法得到。所以前缀积在这里并不是一个干净的解法，真正干净的解法还是要靠动态规划。

2. 从“最大子数组和”到“乘积最大子数组”：核心难点解析

2.1 直接套用加法模型的陷阱

很多人在做这道题之前，都刷过LeetCode 53题“最大子数组和”。那道题的动态规划转移方程非常简洁：

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

含义是：以第 i 个元素结尾的最大子数组和，要么是“从前面延续过来”，要么是“从当前元素重新开始”。因为加法没有正负符号反转的问题，维护一个“最大和”就够了。

我一开始也是这么想的，把加法换成乘法：

dp[i] = max(dp[i-1] * nums[i], nums[i])

然后提交，挂了。原因很快就找到了。比如数组 [-2, 3, -4]，按上面这个状态转移：

• i=0：dp = -2，答案 = -2
• i=1：dp = max(-2*3=-6, 3) = 3，答案 = 3
• i=2：dp = max(3*-4=-12, -4) = -4，答案 = 3

可实际最大乘积是多少？是整个数组 (-2) * 3 * (-4) = 24。为什么漏掉了？因为在 i=1 时，我们放弃了“以 -2 结尾的子数组乘积 -6”，觉得它太小了。可没想到 -6 和后面的 -4 相乘时，负负得正直接变成 24。这就说明：在乘法场景下，一个“看起来很差的最小值”，可能在关键时刻变成“最大值”的种子。加法里没有这种现象，或者说加法中“负数种子”永远翻不了身，但乘法里负数种子有逆袭的机会。

2.2 为什么必须同时维护“最大”和“最小”

核心原因就一句话：乘以一个负数，大小关系会反转。

假设当前维护着一个状态值，它可能是正数也可能是负数。当新的 nums[i] 是正数时，最大值乘以它还是最大，最小值乘以它还是最小，方向不变；但当 nums[i] 是负数时，最大值乘以负数会变成最小的候选，最小值乘以负数反而变成最大的候选。如果我们只盯着最大值，就会把“最小值乘以负数”这个可能的超级选项直接忽略掉。

所以状态定义必须升级成两个：

• fMax[i]：以 nums[i] 结尾的子数组的最大乘积
• fMin[i]：以 nums[i] 结尾的子数组的最小乘积

二者都要维护，因为 fMin[i] 可能在未来某一步“翻身”。

转移方程也要同时考虑三种来源：

fMax[i] = max(fMax[i-1] * nums[i], fMin[i-1] * nums[i], nums[i])
fMin[i] = min(fMax[i-1] * nums[i], fMin[i-1] * nums[i], nums[i])

这里为什么还要单独拿 nums[i] 出来比较？因为子数组是连续的，当前位置可以选择“不延续前面的任何子数组”，而是以自己为起点重新开始。比如前面算出来的乘积是0，或者当前元素比延续过来的乘积更大，都应该从当前元素重新起头。

2.3 用生活类比理解状态同步更新

可以把 fMax 和 fMin 想象成两个口袋：一个装“当前能拿到的最大乘积”，一个装“当前能拿到的最小乘积”。数组每往前走一步，相当于抽一张新牌，然后要把这张牌分别和两个口袋里的值相乘，再看看结果是大还是小。

举个例子，你手里两个口袋分别是 6 和 3，抽到一张牌是 -2，那么：

• 6 * (-2) = -12，这个数会变成最小口袋的有力竞争者
• 3 * (-2) = -6，这个数反而会变成最大口袋的有力竞争者

同时不要忘了，还可以选择“扔掉之前所有牌，只用 -2 重新开始”。这就是和 nums[i] 单独比较的含义。

整个过程像拿着一根绳子，最大值和最小值互相拉扯、彼此托底，缺了哪一个，另一个都会在某次遇到负数时彻底失效。我在实际推导中习惯把每一步的 fMax 和 fMin 都列成表格，这样能直观看到它们如何交替变化，比空想转移方程可靠得多。

3. Java 多种解法实现：从滚动变量到数组DP

3.1 推荐解法：双变量滚动更新

这是面试中最推荐写出来的版本，时间复杂度 O(n)，空间复杂度 O(1)。只维护两个变量，分别表示“以当前元素结尾的最大乘积”和“以当前元素结尾的最小乘积”，每次迭代时使用旧值计算新值，最后更新答案。

public int maxProduct(int[] nums) { int max = nums[0]; int min = nums[0]; int ans = nums[0]; for (int i = 1; i < nums.length; i++) { int curMax = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]); int curMin = Math.min(Math.min(max * nums[i], min * nums[i]), nums[i]); max = curMax; min = curMin; ans = Math.max(ans, max); } return ans; }

这里的核心操作是：把当前的 max 和 min 先保存成局部变量，或者直接用 curMax、curMin 把这些新值算出来，再做赋值。一定不要先更新 max 再使用 max 去更新 min，因为那样会污染计算。

拿 nums = [2, 3, -2, 4] 走一遍：初始化 max=2，min=2，ans=2。i=1 时，max3=6，min3=6，取和3比较得 curMax=6，curMin=3；i=2 时，max=-2 这一轮前最大值是6，min=3，6*(-2)=-12，3*(-2)=-6，和-2比较后 curMax=-2，curMin=-12；i=3 时，max=-2，min=-12，-24=-8，-124=-48，和4比较后 curMax=4，curMin=-48。最终 ans 在 i=1 时取到6，返回6。

3.2 便于理解的辅助数组DP版本

有些朋友不太习惯滚动变量，觉得两个变量之间的更新关系容易绕晕。那可以先写辅助数组版本，思路完全一致，只不过把状态存进数组，方便打印和调试。

public int maxProductWithArray(int[] nums) { int n = nums.length; int[] dpMax = new int[n]; int[] dpMin = new int[n]; dpMax[0] = nums[0]; dpMin[0] = nums[0]; int ans = nums[0]; for (int i = 1; i < n; i++) { dpMax[i] = Math.max(Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]); dpMin[i] = Math.min(Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]); ans = Math.max(ans, dpMax[i]); } return ans; }

这个版本的空间复杂度是 O(n)，面试时可以提一句“可以优化成 O(1)”，然后顺手改成滚动变量版本，观感会很好。从学习角度来说，数组版更容易和状态定义一一对应：dpMax[i] 对应 fMax[i]，dpMin[i] 对应 fMin[i]，调试时把数组打印出来，每一步的变化一目了然。

3.3 巧思版本：负数时交换最大值与最小值

再讲一种很有启发性的写法，思路来自对“乘法反转大小关系”的观察：如果当前元素是负数，那么最大值乘完之后会变成最小值，最小值乘完之后会变成最大值。所以可以先交换 max 和 min，再统一做乘法和比较。

public int maxProductWithSwap(int[] nums) { int max = 1; int min = 1; int ans = Integer.MIN_VALUE; for (int num : nums) { if (num < 0) { int tmp = max; max = min; min = tmp; } max = Math.max(max * num, num); min = Math.min(min * num, num); ans = Math.max(ans, max); } return ans; }

注意这里初始化的技巧：max 和 min 都初始化为1，而不是 nums[0]，因为我们要在循环里统一处理所有元素，包括第一个元素。1乘以任何数都等于它自身，相当于一个恒等变换。

这个版本我第一次看到时觉得很妙，它的本质和双变量版是完全等价的，只是把“负数会让大小反转”这个逻辑显式写了出来。面试时如果能把“为什么负数时交换 max 和 min”解释清楚，面试官通常会很满意。

3.4 暴力法的复杂度分析与参照价值

暴力法代码前面已经给过了，时间复杂度 O(n^2)，空间复杂度 O(1)。它的价值在于验证答案：写完动态规划解法后，可以用暴力法在随机小规模数组上对比结果，确认转移方程没有写错。

我平时验证状态转移方程时，会写一个小的测试脚本，生成随机数组，同时跑暴力解法和动态规划解法，比较结果是否一致。这一步能帮你在提交前把所有边界问题暴露出来。千万别嫌麻烦，算法题里很多“我觉得没问题但提交就错”的情况，都是因为某些隐蔽边界没有覆盖到。

4. 边界条件与常见坑位：这些细节决定成败

4.1 数组长度为1时能否正确处理

当 nums = [-1] 时，任何解法都应该返回 -1。滚动变量版本里初始化 max=min=ans=nums[0]，循环不执行，直接返回 -1。如果初始化的值写错了，比如把 ans 初始化成 0，那么单元素数组 [-1] 就会错误地返回 0。这是最常见的初始化错误。

4.2 初始化值选择：为什么不能用0或Integer.MIN_VALUE

有些同学习惯把 ans 初始化为 Integer.MIN_VALUE，这在很多最大值类题目里是对的，但在乘积题里要小心。假设把 max 或者 min 初始化为0，而数组全是负数，比如 [-1, -2]，那么 max 一开始是0，乘以 -1 还是0，乘以 -2 还是0，最后答案会错误地变成0，而不是真正的2。因为0乘以任何数都是0，这个“0”像一个污染源，会把所有乘积清零。

所以滚动变量版最安全的写法是：max、min、ans 全部初始化为 nums[0]。这样既避免空数组问题，也避免0污染问题。至于“先乘再比较”的交换写法，由于它的设计就是在每一轮统一处理当前元素，所以 max 和 min 初始化为1是安全的，但 ans 必须初始化为 Integer.MIN_VALUE，因为它要在循环里收集每一轮的结果。

4.3 为什么必须单独维护全局答案 ans

动态规划里，fMax[i] 表示“以第 i 个元素结尾”的最大乘积，但最终答案不一定是最后那个元素结尾的子数组。比如 [2, 3, -2, 4] 里最大乘积 6 是以第1个元素结尾的子数组 [2,3] 产生的，而不是以最后一个元素结尾的。所以必须用一个额外的 ans，在每一轮迭代中记录历史最大值。

这一点和“最长递增子序列”之类的问题很像：状态定义是“以 i 结尾”的，但答案要扫描所有状态取最大值。如果直接用最后一个 fMax 作为答案，遇到最大答案在中间出现的情况就会出错。

4.4 滚动更新的先后顺序：先算后赋，避免污染

如果在双变量版里这样写：

max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]); min = Math.min(Math.min(max * nums[i], min * nums[i]), nums[i]);

第二行里的 max 已经是更新过的值了，它是“以当前元素结尾的新 max”，再拿它去和 min 相乘，逻辑就乱了。正确做法是用 curMax 和 curMin 两个局部变量同时保存新值，或者先把旧值备份出来。这个坑不亲自踩一次很难注意到，因为它不报错，只是答案偶尔不对。

4.5 关于溢出的思考

这道题在LeetCode的数据范围下，int 是够用的。但实际面试中，如果数组元素很大或者很长，乘积可能超过 int 范围。可以提一句“如果数据范围更大，把变量类型换成 long，或者结合说明使用合适的数据结构”，面试官通常会觉得你有工程意识。不过不要过度设计，LeetCode 环境里用 int 是标准做法。

5. 相似题型与进阶扩展：刷一道顶五道

5.1 和LeetCode 53题“最大子数组和”的对比

把两道题放在一起看，是最有效的学习方式。最大子数组和的转移方程只需要一个 dp 值，因为加法中负数的符号效应不会反转大小关系。最大子数组乘积则必须维护两个值，核心变量是“负负得正带来的大小反转”。

对比表格：

这个对比在面试中非常有用。面试官如果先让你写53题，然后让你写152题，你要能清晰说出“为什么53题的思路不能直接套过来”，这比闷头写对代码更分。

5.2 进阶变体：返回最大乘积子数组本身

有时候面试官会追问：不只返回最大值，还要返回这个子数组。思路是在滚动更新的同时记录边界下标。每当 ans 被更新时，记录当前的结束下标；同时维护当前最优片段的起始下标。因为负数翻转会让“最优起点”变得复杂，通常记录区间的方法是：在每次“从当前元素重新开始”时更新候选起点，在每次 ans 被更新时固定答案区间。这个代码比纯返回值要长一些，但核心逻辑完全一致，有兴趣的读者可以自己实现一遍。

5.3 其他变体思路

还有一类变体是求“乘积最小的连续子数组”，只需要把状态转移中 max 和 min 的角色对调，其他完全不变。以及考虑环形数组时的最大乘积子数组问题，通常做法是拆成两种情况：不跨越边界的最大乘积，以及跨越边界的情况（通过求最小子数组乘积，再用总乘积除以最小子数组乘积来得到跨越边界的最大乘积）。当然这里要注意除以零的问题，遇到0还得单独处理。

这些变体没有必要全刷一遍，但理解了152题的核心思想后，遇到它们都能快速迁移。动态规划题就是这样，代码量不大，难的是状态定义和不同场景下的变化逻辑，吃透一道经典题的价值远大于囫囵吞枣刷十道简单题。

我个人在实际练习中的体会是：这题第一次做错非常正常，重点是要把错误对照着“负负得正”这个本质去复盘。找一个包含正数、负数、零的测试用例，把每一步 fMax 和 fMin 都手算出来，写一次表格，以后再遇到同类题基本就不会慌了。如果面试时能主动讲出“为什么需要两个状态”和“负数如何导致大小反转”，这题基本上就拿下了。