企业官网建设流程全解析

最近刷 LeetCode 热题 100 刷到第 84 题“乘积最大子数组”，这道题在动态规划专题里挺有代表性，也是面试中很容易被拿出来做变体考察的一道题。乍一看它和“最大子数组和”很像，都是求连续子数组的最优值，但真上手写状态转移的时候就会发现，乘积的性质让问题复杂了不少——负数、零、小数都能让结果瞬间翻转。这篇就结合我自己刷题和给同事讲题的经验，把这个题从暴力到动态规划、从一维到空间压缩、从只能求值到能回溯出具体子数组，完整拆一遍。

1. 题目理解与核心思路拆解

先看题目本身：给定一个整数数组，找出数组中乘积最大的连续子数组，返回这个最大乘积。比如输入[2,3,-2,4]，答案是 6，对应子数组[2,3]。再比如[-2,0,-1]，答案是 0，因为最大乘积就是 0。

这道题之所以比“最大子数组和”难，关键就在“乘积”这两个字上。求和的时候，子数组的最优解只跟当前元素前面的最大和有关系，因为加法是单调的：前面和越大，加上当前元素一定越大。但乘积不一样，乘法是有“符号翻转”的。负数乘负数得正数，一个很小的负数子数组乘积，可能乘上另一个负数就变成很大的正数。所以如果只盯着“最大乘积”这一个状态，一定会漏掉负数跟负数相乘的机会。

这里可以先想暴力做法：枚举所有子数组起点终点，逐个算乘积，时间复杂度 O(n²) 或者 O(n³)，数据量小还能应付，一旦到 10 万级别的数组直接超时。面试时如果张口就是暴力，基本就告别下一轮了。所以需要用动态规划来消除重复计算。

那动态规划状态该怎么定义？既然乘法有正负翻转的特性，我们不仅要记录“以当前位置为结尾的最大乘积”，还要记录“以当前位置为结尾的最小乘积”。为什么需要最小值？因为它代表了“潜力股”——当前虽然是最小，甚至是负数，但只要下一个元素也是负数，两者相乘就可能变成最大值。这就是这个题最核心的思路：同时维护最大和最小，二者互为对方的备胎。

具体来说，用max_dp[i]表示以nums[i]结尾的子数组的最大乘积，min_dp[i]表示以nums[i]结尾的子数组的最小乘积。那么状态转移就是：

max_dp[i] = max(nums[i], max_dp[i-1] * nums[i], min_dp[i-1] * nums[i]) min_dp[i] = min(nums[i], max_dp[i-1] * nums[i], min_dp[i-1] * nums[i])

为什么一定要和nums[i]本身比较？因为子数组必须连续，如果前面乘出来是负的、当前元素是正的，那从当前元素重新开始子数组，nums[i]本身可能比max_dp[i-1] * nums[i]更大；反过来，如果前面的最大乘积是正的，当前元素也是正的，那乘起来更大；如果前面乘积很大是正的，当前元素是负的，乘完之后变成负的，这时候最小乘积就要更新。所以三个候选缺一不可。

一句话概括思路：不要只贪心记录目前最好的，也要记住目前最坏的，因为最坏的翻个身可能就是最好的。

2. 动态规划解法详解与代码实现

思路清楚了，写代码就是水到渠成的事。这里我用 Python 来写，因为刷题时 Python 表达最简洁，面试时也最好解释。

def maxProduct(nums): if not nums: return 0 max_dp = [0] * len(nums) min_dp = [0] * len(nums) max_dp[0] = nums[0] min_dp[0] = nums[0] result = nums[0] for i in range(1, len(nums)): cur = nums[i] max_dp[i] = max(cur, max_dp[i-1] * cur, min_dp[i-1] * cur) min_dp[i] = min(cur, max_dp[i-1] * cur, min_dp[i-1] * cur) result = max(result, max_dp[i]) return result

这段代码很简单，但有几个细节值得展开讲。

第一，为什么max_dp和min_dp要用数组存？因为状态转移只依赖前一个位置，其实可以只用两个变量滚动更新，但用数组的好处是方便我们调试时打印每一步的状态，也能直接回溯出最优子数组。面试时如果只要求返回最大值，建议先用数组版讲清楚逻辑，再优化成滚动变量，这样能展示你既懂原理又会优化。

第二，初始化时result不能设为0。有些同学写result = 0，然后遍历更新，遇到全负数数组就会出错。比如[-2, -3]，最大乘积是 6，但如果你一开始result = 0，第一步max_dp[0] = -2小于 0，result还是 0，最后返回 0 就错了。所以初始值必须和第一个元素绑定，result = nums[0]是标准做法。

第三，状态转移里max和min函数的参数都是三个，不要漏掉cur本身。有些简化的写法会用max(max_dp[i-1] * cur, min_dp[i-1] * cur)，然后单独判断和cur的大小。这样写逻辑一样，但三个参数一起取最值更不容易漏。注意这里cur就是nums[i]，不是前一个位置的乘积，因为子数组可以从当前位置重新开始。

下面用一个例子完整走一遍状态转移过程，帮助理解。以nums = [2, 3, -2, 4]为例。

• 初始化：max_dp[0] = 2，min_dp[0] = 2，result = 2。
• i = 1，cur = 3：
  • max_dp[1] = max(3, 2*3, 2*3) = 6。
  • min_dp[1] = min(3, 2*3, 2*3) = 3。
  • 更新result = max(2, 6) = 6。
• i = 2，cur = -2：
  • max_dp[2] = max(-2, 6*(-2), 3*(-2)) = max(-2, -12, -6) = -2。
  • min_dp[2] = min(-2, 6*(-2), 3*(-2)) = min(-2, -12, -6) = -12。
  • 注意这里最大乘积变成了-2，看似糟糕，但最小乘积-12被记录下来了。
• i = 3，cur = 4：
  • max_dp[3] = max(4, (-2)*4, (-12)*4) = max(4, -8, -48) = 4。
  • 等等，这里算出来最大是 4？那结果应该还是 6。没错，[2,3]的乘积 6 是最大的，后面[-2,4]乘积是 -8，[2,3,-2,4]整体乘积是 -48，都不如 6 大。

如果数组是[-2, 3, -4]，走一遍看负负得正的效果：

• 初始化：max_dp[0] = -2，min_dp[0] = -2，result = -2。
• i = 1，cur = 3：
  • max_dp[1] = max(3, -2*3, -2*3) = 3。
  • min_dp[1] = min(3, -2*3, -2*3) = -6。
  • result = max(-2, 3) = 3。
• i = 2，cur = -4：
  • max_dp[2] = max(-4, 3*(-4), (-6)*(-4)) = max(-4, -12, 24) = 24。
  • min_dp[2] = min(-4, 3*(-4), (-6)*(-4)) = min(-4, -12, 24) = -12。
  • result = max(3, 24) = 24。

这里就很清楚了：如果没有min_dp记录下-6，走到-4的时候你根本不知道前面有一段乘积是-6，更不可能算出 24。这就是同时维护最大最小的价值。

复杂度方面，时间 O(n) 遍历一次，空间 O(n) 如果存两个数组，优化后 O(1)。这是标准的动态规划题解，面试时先讲 O(n) 空间版，再优化到 O(1)，通常已经够用了。

3. 空间优化与“只维护变量”的写法

数组版的好理解，但真正提交代码很多人会写成滚动变量版本。max_dp[i]只依赖max_dp[i-1]，min_dp[i]只依赖min_dp[i-1]，所以完全可以只用两个变量pre_max和pre_min，边遍历边更新。

def maxProduct(nums): if not nums: return 0 pre_max = nums[0] pre_min = nums[0] result = nums[0] for i in range(1, len(nums)): cur = nums[i] # 注意先用临时变量保存上一轮的 pre_max，避免更新 pre_min 时用了新的 pre_max cur_max = max(cur, pre_max * cur, pre_min * cur) cur_min = min(cur, pre_max * cur, pre_min * cur) pre_max = cur_max pre_min = cur_min result = max(result, pre_max) return result

这里有个非常关键的细节，也是很多新手会踩的坑：更新pre_min的时候，必须使用旧的pre_max，而不是刚更新完的新pre_max。如果写成：

pre_max = max(cur, pre_max * cur, pre_min * cur) pre_min = min(cur, pre_max * cur, pre_min * cur) # 错误：pre_max 已经是新值了

就会导致状态错乱。因为pre_min的转移需要max_dp[i-1] * nums[i]，也就是旧的pre_max，如果pre_max先被更新成当前轮的新值，再参与pre_min计算，等于用错了前一个状态。所以要么先用临时变量保存旧值，要么把pre_max和pre_min的计算写在同一行里通过 Python 的元组同时赋值。比如：

pre_max, pre_min = max(cur, pre_max * cur, pre_min * cur), min(cur, pre_max * cur, pre_min * cur)

Python 的元组赋值会先计算右侧所有表达式，再统一赋值，所以右侧的pre_max和pre_min都是旧值，这样写没问题。但为了可读性，我建议用临时变量，因为面试官不一定熟悉这种语法，而且解释起来更直白。

再说说为什么要做空间优化。从算法角度看，O(n) 和 O(1) 在数据规模大时差异明显；从面试角度看，主动做空间优化能体现你对动态规划的掌握程度。不过有一点要强调：空间优化后，我们就丢失了每个位置的max_dp和min_dp历史值，如果题目要求输出具体的子数组（比如“找出最大乘积对应的连续子数组”），就需要额外的记录方式。这一点下面单独讲。

除了空间优化，另一个常见变体是允许数组中含有 0。如果数组里有 0，乘积会归零，这在状态转移里会自动处理吗？会的。比如[2, 3, 0, 4]，当cur = 0时：

• max_dp = max(0, pre_max * 0, pre_min * 0) = 0。
• min_dp = min(0, pre_max * 0, pre_min * 0) = 0。

后面再遍历4时，因为前面状态是 0，乘积要么是 4 要么是 0，结果 0 会被保留下来。所以代码天然兼容 0 的情况，不需要特殊处理。这也算这个题设计的一个微妙点——如果你在状态转移时把“跳过 0”当作特殊逻辑来处理，反而容易写错。直接一视同仁地套用三个候选取最值，0 就会被正确“切断”连续子数组。

不过要注意，0 的存在会影响“最小乘积”的含义。当遇到 0 后，pre_max和pre_min都会变成 0，这时候以 0 为结尾的子数组最大和最小都是 0，相当于重新开始。这个行为是符合子数组连续性的：如果跨过 0，乘积就变成 0，不可能更优，所以最优子数组要么在 0 左侧，要么在 0 右侧，要么就是包含 0 的某个单元素子数组。动态规划通过状态重置巧妙地完成了“自动分段”，不需要手动 split 数组。

4. 进阶：如何回溯输出最大乘积的连续子数组

LeetCode 原题只要求返回最大乘积，但我在实际项目里遇到过类似需求，要求知道到底是哪一段子数组产出了这个最大值。比如给一段传感器数据做连续采样窗口分析，要找乘积最大的窗口。这时候只返回数值就不够了，需要把子数组的起止下标也找出来。

思路是：在动态规划滚动更新时，额外维护“当前最大乘积对应的子数组起点”。但这里有个坑，因为最大乘积可能来源于pre_max * cur、pre_min * cur或者cur本身，而起点的继承方式不同。如果是pre_max * cur或pre_min * cur，说明当前子数组是从之前的起点延续过来的；如果是cur，说明子数组重新从当前位置开始。

为了记录起点，最简单的方法是不做空间优化，保留max_dp数组和min_dp数组，同时再用两个数组记录每个位置对应的起点下标。但更实用的做法是，在得到最终最大值后，用一次反向扫描来定位子数组。

反向定位的思路是这样的：先用空间优化版本求出最大乘积result，然后从右往左遍历数组，维护一个“从当前位置到某个右端点 R 的乘积”。假设我们枚举右端点 R，从 R 往左扩展，一旦找到乘积等于result的区间，直接记录下标。虽然最坏情况 O(n²)，但实际场景中往往很快命中。如果追求稳定 O(n)，那就需要保存状态数组。

我自己更推荐一种更优雅的写法：在滚动更新的同时，用两个额外变量start_max和start_min记录当前pre_max和pre_min对应子数组的起点。每次决策时，如果cur胜出，起点就更新为i；如果pre_max * cur胜出，起点沿用pre_max的起点；如果pre_min * cur胜出，起点沿用pre_min的起点。同时还需要维护全局result对应的全局start和end。这样一轮遍历就能同时拿到最大值和区间下标。

具体代码稍长，但逻辑清晰，面试时如果能在讲完标准解法后补充这个变体，通常会是很加分的亮点。我贴一个参考实现：

def maxProductWithSubarray(nums): if not nums: return 0, (-1, -1) pre_max = nums[0] pre_min = nums[0] # 分别记录 pre_max 和 pre_min 对应子数组的起点 max_start = 0 min_start = 0 result = nums[0] res_start = 0 res_end = 0 for i in range(1, len(nums)): cur = nums[i] # 计算新的最大值 candidates = [ (cur, i), (pre_max * cur, max_start), (pre_min * cur, min_start) ] cur_max, cur_max_start = max(candidates, key=lambda x: x[0]) # 计算新的最小值 candidates_min = [ (cur, i), (pre_max * cur, max_start), (pre_min * cur, min_start) ] cur_min, cur_min_start = min(candidates_min, key=lambda x: x[0]) pre_max, max_start = cur_max, cur_max_start pre_min, min_start = cur_min, cur_min_start if pre_max > result: result = pre_max res_start = max_start res_end = i return result, (res_start, res_end)

这段代码有个细节值得注意：max和min的key函数要用x[0]，否则元组比较会先比较第一个元素，相同时再比较第二个元素，可能引起歧义。另外在计算cur_min时，pre_max和pre_min还是旧值，因为这里没有先更新它们；如果你在代码里先更新了pre_max再计算cur_min，就会踩到前面说的“用错旧值”的坑。所以这个实现里我故意把cur_max和cur_min都先用临时变量算完，再统一赋值给pre_max和pre_min。

实测一下：

• 输入[2, 3, -2, 4]，输出(6, (0, 1))，正确。
• 输入[-2, 3, -4]，输出(24, (0, 2))，因为整个数组乘积就是 24，正确。
• 输入[0, 2, 3]，输出(6, (1, 2))，正确。

如果面试时非要追求空间 O(1) 且时间 O(n)，这个版本就是最优解。但说实话，面试现场能把这个起点追溯逻辑一次写对的人不多，平时建议多练几遍。如果觉得不够熟练，可以先写保存数组的版本，再优化到这个滚动版本，保证思路清晰。

5. 常见错误、边界情况与调试技巧

刷题最宝贵的经验就是从错误里总结套路。这个题我见过太多人栽跟头，这里把典型错误和对应场景整理成表格，方便自查。

逐条说一下我觉得最值得注意的几点。

第一，初始化问题。除了result要取nums[0]，pre_max和pre_min也必须初始化为nums[0]，不能初始化为 0 或 1。初始化为 0 会导致第一轮循环时pre_max * cur = 0干扰计算；初始化为 1 会影响乘积的起点判断。比如nums = [2, 3]，如果pre_max = 1，第一轮max(3, 1*3, 1*3) = 3，看起来没问题，但如果nums = [0.5, 2]（题目通常不要求小数，但变体题可能出现），pre_max = 1会让1*2=2不正确，因为子数组不能凭空从 “1” 开始。所以规范做法是初始化为第一个元素。

第二，更新顺序错误。我在本地调试时专门复现过这个坑：错误的滚动更新会让结果偏大或偏小，而且很难一眼看出。举个例子，nums = [2, -1, -3]，错误版可能算出 6，正确结果也是 6，看起来一样；但换一组nums = [2, -2, -1]，错误版可能算出 4，正确结果应该是 4？所以有时候错误结果恰好和正确结果一致，这种“巧合”比明显报错更危险。实际调试时，建议在循环里把每轮的pre_max、pre_min打印出来，跟数组版的结果逐行对比，能快速定位问题。

第三，边界情况。LeetCode 的测试用例通常会包含长度 1 的数组、全部负数、包含 0、最大值出现在子数组中间等场景。我的自查清单是：先跑一遍[-2]看结果是不是 -2；再跑[-2, -3]看结果是不是 6；再跑[-2, 0, -1]看结果是不是 0；再跑[2, -5, -2, -4, 3]这种正负交替，手动算一遍答案。这些用例覆盖了最核心的边界逻辑。另外，如果题目允许数组中有小数，还要额外小心乘积的精度问题和浮点数比较，一般 Python 的 float 在处理简单乘法时没问题，复杂场景要考虑用Decimal或判断科学计数法，不过 LeetCode 原题数组中都是整数，这个问题实际不会遇到。

第四，debug 技巧。动态规划题最怕“肉眼 debug”，尤其是状态多的时候。我的经验是把状态转移表画出来，横轴是数组下标，纵轴是max_dp、min_dp，每填一格就对照公式检查。有一次我在一个变体题里搞错了“子数组可以为空”的语义，导致空数组状态参与转移，画表之后立刻发现了问题：max_dp[i]不应该允许从空数组继承乘积 1。这类错误在代码里根本看不出来，但状态表一看就懂。

还有一个容易被忽略的点：题目要求的是“连续子数组”，所以状态转移时不能跳过元素。有些同学会联想到“乘积最大子序列”（可以不连续）的解法，把状态定义成“前 i 个元素中的最大乘积”，这样就会算错。记住，这里dp[i]定义的是“以 nums[i] 结尾”的连续子数组，不是“前 i 个元素中任意选取”。这个区别决定了状态转移方程的形式。我在给别人讲解时经常强调一点：动态规划的状态定义直接决定了转移方程的写法，如果转移方程写不出来，先回头检查状态定义是不是有问题。

6. 经验心得：这道题在面试里怎么答才能加分

刷题归刷题，最终还是要落到面试和实际工作里。这里分享一些我在这道题上的面试经验，以及它跟其他题目的联系。

先说面试答题的节奏。拿到题先别急着写代码，先用一两句话说思路：这是一个动态规划问题，因为需要记录以每个位置为结尾的最大乘积，同时因为乘积有符号翻转的特性，还要维护最小乘积。然后举一个简单例子，比如[-2, 3, -4]，手动演示为什么只维护最大值会漏掉 24。这样面试官能立刻理解你不是背答案，而是真的明白原理。

接下来写代码时，建议先写数组版，讲清楚状态定义和转移方程，再自己主动说“这里可以优化到 O(1) 空间”，然后改成滚动变量版本。这个加分项一定不要放过。最后面试官大概率会追问：如果数组里有 0 怎么办？如果要求输出子数组本身怎么办？如果允许子数组为空怎么办？这些问题在本文前面都覆盖到了，按照对应思路回答即可。

还有一个小考点：为什么这道题不能用“最大子数组和”的经典贪心解法？经典解法只用一个变量累加当前和，如果当前和小于 0 就重置为 0，因为加法中负数对后续只有坏处。但在乘积中，负数对后续可能是好处，尤其是连续两个负数时。所以贪心思路在这里失效，必须用动态规划维护两个状态。面试时如果能把这两种场景对比着讲清楚，说明你对动态规划的“状态设计”理解到位了，比单纯记住代码强得多。

另外，这道题和很多题有联系。比如“乘积最大子序列”（不要求连续）是完全不同的思路；而“最大子数组和”是它的简化版；“股票价格最大利润”也涉及一维状态机；还有“最长递增子序列”也是经典一维 DP。刷题时建议把这些题放在一起做对比总结，你会发现动态规划的套路其实是相通的：定义状态、写转移方程、处理边界、优化空间。

在实际工作中，这种“同时维护最大最小值”的思想也非常有用。比如在做数值计算时，如果一个操作可能产生符号翻转（乘法、取反、角度归一化等），或者一个操作的效果依赖于前序状态的反向变化，就可以借鉴这种双状态维护的思路。我之前做一个数据标准化模块时，需要计算滑动窗口内数值的乘积趋势，当时第一个想到的就是这道题的解法。虽然最终因为业务逻辑复杂用了其他方案，但“维护最小状态做备用”的思路给了我很大启发。

最后我想说，刷题不是背题，而是理解题目背后的思维模型。乘积最大子数组这道题，难度不高不低，正好适合用来练习动态规划的状态设计。如果你现在刷这道题觉得卡壳，很正常，我当初也栽过跟头。我的建议是，先别看题解，自己试着用“最大最小两个状态”去推导，哪怕写不出来，也比直接看答案强。等你推导出正确的转移方程，再回来看这篇文章的代码，会感觉每一行都有它的位置存在。这种“顿悟”的时刻，才是刷题最爽的瞬间。