企业官网建设流程全解析

这道题我一开始做的时候，以为就是个“最长连续子数组”的变体，心想这不就是双指针扫一遍的事吗？结果连着提交几次都没过，才意识到问题出在“乘积为正数”这四个字上。LeetCode 1567 的核心难点，不在于找最长子数组长度，而在于一个负数就能让整个乘积的正负号翻过来，一个零又能让一切清零重来。题目本身适合所有正在刷动态规划、准备面试的读者，尤其是如果你刷过 152 乘积最大子数组但总感觉状态设计没吃透，这道题能把“状态到底该存什么”这件事讲得很清楚。下面我把自己从读题到一次 AC 的完整过程拆开讲，顺便把踩过的坑都标出来。

1. 乘积为正数到底难在哪：题意拆解与核心观察

1.1 一句话看懂题目

题目给你一个整数数组nums，要你找出一个连续的子数组，使得这个子数组内所有数字的乘积是正数，并且子数组长度尽可能长，返回这个最长长度。注意是“子数组”，意味着必须是连续的，不是子序列，不能跳着选。比如：

nums = [1, -2, -3, 4] 输出：4

因为整个数组[1, -2, -3, 4]的乘积是 24，是正数，所以最长长度就是 4。再比如：

nums = [0, 1, -2, -3, -4] 输出：3

这里[-2, -3, -4]乘积是 -24，不行；但[1, -2, -3]乘积是 6，正数，长度 3。[-2, -3]长度 2 也是正数，但不够长。0 在这里很尴尬，它会把数组切成两段，任何包含 0 的子数组乘积都是 0，既不是正数也不是负数，所以 0 只能是断点。

我刚做这题的时候第一反应是：维护一个“当前乘积”不就好了？大于 0 就长度加一，小于 0 就重置。然后很快就发现这个思路完全不行，因为负数带来的“延时翻转”效应，会让贪心在局部失效。

1.2 为什么“一直乘下去”的思路行不通

如果数组全是正数，答案就是整个数组长度，这道题就直接变送分题了。但一旦出现负数，事情就变得微妙。假设数组是[-1, -2, -3]，如果你从 -1 开始乘，乘积是 -1，为负；继续乘 -2，乘积变 2，为正；再乘 -3，乘积变 -6，又变负。你会发现：

• 负数个数的奇偶性，直接决定最终乘积的符号。
• 单个负数的长度贡献可能是“负的”，但再遇到一个负数，之前积累的长度就全“翻正”了。

这就好比你在一段路上走，标记是“正”或“负”，每走一步看当前方向。但这条路不是你从起点一路走到终点就完了，你可以从任意位置开始、任意位置结束。问题就变成了：在所有连续区间里，找到最长的“负号个数为偶数”的区间。但是注意，区间里如果有一个 0，它会让乘积直接归零，负号个数的奇偶性规则就失效了，所以必须把 0 当成分隔符看。

这个“偶负号 + 无零”的观察，是这道题最核心的突破口。动态规划的做法，本质上就是围绕这个观察在维护信息。

1.3 最小子问题：我只需要知道“以 i 结尾”的情况

动态规划里最常用的一个思维工具，就是只考虑“以当前位置结尾的所有子数组”。为什么只看结尾不看开头？因为子数组的连续性使得“结尾”能天然承接上一个位置的状态，而“开头”的选择可以交给状态转移自动处理。

比如我们固定nums[i]是子数组的最后一个元素，那么所有以它结尾的子数组，要么只包含它自己，要么就是“以nums[i-1]结尾的某个子数组”再接上nums[i]。这样一来，我只需要知道：

• 以nums[i-1]结尾的、乘积为正的子数组，最长有多长；
• 以nums[i-1]结尾的、乘积为负的子数组，最长有多长。

有了这两个长度，再加上nums[i]本身的正负，就能推出nums[i]结尾的正负长度。这就是整道题 DP 状态的由来。

2. 动态规划思路：把“符号”也写进状态里

2.1 状态定义：pos[i] 和 neg[i]

很多人在 152 乘积最大子数组里吃过亏，因为那个题要同时维护“最大值”和“最小值”，否则负数一乘就翻车。1567 的思路类似，但状态更直白一点：我们不用存乘积的最大最小值，因为这里只关心符号，不关心数值大小。

定义两个数组：

pos[i]：以 nums[i] 结尾的、乘积为正数的最长子数组长度。 neg[i]：以 nums[i] 结尾的、乘积为负数的最长子数组长度。

这里有个很关键的细节：这两个长度都是“以 nums[i] 结尾”，所以每个状态天然包含nums[i]这个元素。如果不存在这样的子数组，长度记为 0。举个例子，nums = [ -1, 2 ]，那么：

• pos[0] = 0，因为以 -1 结尾的正积子数组不存在；
• neg[0] = 1，因为 [-1] 乘积为负，长度 1；
• pos[1] = 1，因为 [2] 乘积为正，长度 1；
• neg[1] = 2，因为 [-1, 2] 乘积为负，长度 2。

看到没有，neg[1]是靠前面的“负积状态”继承过来的：nums[1]是正数，不会改变符号，所以之前为负，现在还是为负。

2.2 三个转移分支：正数、负数、零

定义好状态之后，转移就很自然了。逐个看nums[i]的三种情况。

情况一：nums[i] > 0。正数乘以任何数都不改变符号，所以：

pos[i] = pos[i-1] + 1 // 之前如果为正，接上正数还是为正 neg[i] = neg[i-1] > 0 ? neg[i-1] + 1 : 0

第二行的意思是：如果前面有“负积子数组”，接上这个正数，负号保留，长度加一；如果前面没有负积子数组，那么当前元素无法单独形成负积，所以记为 0。

情况二：nums[i] < 0。负数会翻转符号，这是整个题的核心：

pos[i] = neg[i-1] > 0 ? neg[i-1] + 1 : 0 neg[i] = pos[i-1] + 1

第一行：前面要是有负积子数组，接上这个负数，负负得正，变成正积，长度加一；如果前面没有负积子数组，单个负数乘积为负，不可能形成正积，所以是 0。

第二行：前面不管有没有正积子数组，只要pos[i-1]是一个非负长度，那么pos[i-1] + 1都是安全的。如果pos[i-1] = 0，说明前面没有以nums[i-1]结尾的正积子数组，那当前这个负数自己就构成“负积子数组”，长度为 1，所以neg[i] = 1；如果pos[i-1] > 0，则接在正积子数组后面，负负得负，长度为pos[i-1] + 1。这两种情况统一写成pos[i-1] + 1是对的。

情况三：nums[i] == 0。0 是断点，任何包含 0 的子数组乘积都是 0，所以：

pos[i] = 0 neg[i] = 0

说白了就是“从这重新开始”。

2.3 关键细节：为什么“负数”是翻转而不是重置

我在面试里被问到这道题时，很多人会困惑：遇到负数，为什么不直接把长度清零？这里必须想明白一个事：负数不是终点，只是把符号翻转。[-1, -2]这个子数组，乘积是 2，是正的；[-1, -2, -3]乘积又是负的。负数就像一个开关，每按一次，正负掉换。

所以当你处理nums[i] < 0时，你做的不是“清零”，而是把“正积长度”和“负积长度”互换之后再延伸。这点和 152 乘积最大子数组里“遇到负数时交换最大值和最小值”是同一个道理。如果你只维护一个变量，比如只维护正积长度，遇到 -1 的时候你都不知道把谁乘进来，因为之前积累的正积长度碰到负数会变成负积，要等下一个负数才能翻回来。这也是为什么这个题必须同时维护正、负两个状态。

2.4 边界值：pos[0] 和 neg[0] 怎么给

当i = 0时，只有单个元素，没有前面的状态。可以直接按规则初始化：

if nums[0] > 0: pos[0] = 1 neg[0] = 0 elif nums[0] < 0: pos[0] = 0 neg[0] = 1 else: pos[0] = 0 neg[0] = 0

也可以把pos[-1]和neg[-1]虚拟成 0，然后循环从 0 开始，用统一公式推。我建议在代码里直接用两个变量迭代，从i = 0开始处理，这样不需要额外处理数组越界，后面第 3 节会给出完整代码。

3. 代码实现：从 O(n) 空间到 O(1) 空间

3.1 先写一版最直观的 DP 数组版

动态规划的代码有时看着简单，但写着写着就容易乱。我建议先写一版开数组的，把状态转移逻辑理清楚，再去做空间优化。下面这份是 Python 版本，直接对应上面第 2 节的转移公式：

class Solution: def getMaxLen(self, nums: List[int]) -> int: n = len(nums) pos = [0] * n # 以 i 结尾，乘积为正的最长长度 neg = [0] * n # 以 i 结尾，乘积为负的最长长度 if nums[0] > 0: pos[0] = 1 elif nums[0] < 0: neg[0] = 1 ans = pos[0] # 别忘了答案至少包含第一个元素的可能 for i in range(1, n): x = nums[i] if x > 0: pos[i] = pos[i - 1] + 1 neg[i] = neg[i - 1] + 1 if neg[i - 1] > 0 else 0 elif x < 0: pos[i] = neg[i - 1] + 1 if neg[i - 1] > 0 else 0 neg[i] = pos[i - 1] + 1 else: pos[i] = 0 neg[i] = 0 ans = max(ans, pos[i]) return ans

这份代码的时间复杂度是 O(n)，空间复杂度 O(n)。你注意一个细节：neg[i] = pos[i-1] + 1这里我直接加 1，没有判断pos[i-1]是否为 0，因为当pos[i-1] = 0时结果正好是 1，表示“当前这个负数单独形成一个负积子数组”，逻辑是自洽的。

但pos[i] = neg[i-1] + 1 if neg[i-1] > 0 else 0不能省略判断。原因很简单：如果前面没有负积子数组，当前单独一个负数乘积是负的，不是正的，不能记成 1。这个不对称很容易被忽略，也是很多人写错的地方。

3.2 空间压缩到 O(1) 的写法

观察转移公式可以发现，pos[i]和neg[i]只依赖pos[i-1]和neg[i-1]，完全不需要保留整个数组。用两个变量滚动更新就行：

class Solution: def getMaxLen(self, nums: List[int]) -> int: pos = 0 # 当前元素结尾的正积最长长度 neg = 0 # 当前元素结尾的负积最长长度 ans = 0 for x in nums: if x > 0: pos = pos + 1 neg = neg + 1 if neg > 0 else 0 elif x < 0: # 先保存旧值，因为后面的更新会覆盖 old_pos, old_neg = pos, neg pos = old_neg + 1 if old_neg > 0 else 0 neg = old_pos + 1 else: pos = 0 neg = 0 ans = max(ans, pos) return ans

这版代码就是最终提交版本，空间复杂度 O(1)。有人可能会问，neg = old_pos + 1这里如果old_pos = 0会得到 1，没问题吗？没问题是没问题的，但你要想清楚为什么：遇到负数时，即使前面没有正积子数组，当前负数自己也构成一个长度为 1 的负积子数组，所以赋 1 是正确的。

真正需要注意的反而是pos = old_neg + 1 if old_neg > 0 else 0，这个必须判断。因为单个负数的乘积是负的，不能作为正积长度的起点。

3.3 网上流行的 swap 写法为什么会踩坑

不少题解会写一个看起来很简洁的版本：遇到负数就把pos和neg交换，然后两个都加一。乍看之下好像很合理，因为负数翻转正负嘛。但如果你没处理边界，很容易翻车。

我给你演示一下错误版本：

for x in nums: if x < 0: pos, neg = neg, pos pos += 1 neg += 1 elif x > 0: pos += 1 neg = neg + 1 if neg else 0 else: pos = neg = 0

这段代码在nums = [-1]时输出 1，但正确答案应该是 0。因为 [-1] 的乘积是负数，不存在正积子数组。这里的坑就在于：交换之后，pos可能来自原来的neg=0，此时pos + 1 = 1，它错误地认为单个负数能贡献正积。要补救也不是不行，但需要额外判断旧neg是否为 0，反而把事情搞复杂了。

所以我的建议是：面试时老老实实用上面那份“先保存旧值再分别更新”的写法，逻辑清楚，不容易在边界上出问题。代码稍微长一点，但面试官要的是正确性和思路，不是看你炫技。

4. 测试用例：把边界情况按在地上摩擦

4.1 单元素、全零、全负

一道题能不能 AC，边界测试很重要。我把自己反复用到的几组用例列出来，你可以直接当回归用例用。

输入: [1] 输出: 1 输入: [-1] 输出: 0 输入: [0, 0, 0] 输出: 0 输入: [-1, -2, -3] 输出: 2

最后这个例子很多人会答错。[-1, -2, -3]里，[-1, -2]乘积 2 为正，长度 2；[-2, -3]乘积 6 为正，长度 2；[-1, -2, -3]乘积 -6 为负，不能要。所以答案是 2。这个用例能很好检验你对“负数个数奇偶”的理解。

4.2 零作为分隔符的经典场景

零是这道题最大的陷阱，因为乘积里一旦出现 0，整个乘积就归零了。也就是说，零必须把左右两侧完全切开。比如：

输入: [1, 2, 3, 0, -1, -2] 输出: 3

0 左边是[1, 2, 3]，乘积为正，长度 3。0 右边是[-1, -2]，乘积为正，长度 2。答案是 3。你可能会想，能不能跨过 0 取[3, 0, -1, -2]？不行，因为乘积含 0，不是正数。所以遇到 0 时必须把pos和neg都重置为 0，这既是转移公式的要求，也是业务语义的要求。

再来一个更刁钻的：

输入: [0, -1, -2, 0, 3] 输出: 2

左右两侧分别看，左侧[-1, -2]长度 2，右侧[3]长度 1，答案 2。如果代码里 0 处理不当，很可能会错误地把-1, -2, 0, 3连起来算，输出 4，那就错了。

4.3 与类似题目的对比：为什么 1567 不能套用 152 的模板

刷题多了你会发现，1567 和 152 乘积最大子数组特别像，都是要连续子数组，都涉及负数翻转。但两者有一个本质区别：152 需要维护乘积的“最大”和“最小”，因为负负得正之后，最小的负数乘一个负号可能变成最大的正数，但数值大小还会影响后续结果；1567 只关心正负符号，不关心乘积具体是多少，所以只需要维护两个布尔性质的长度。

另外热词里还刷到过 5 最长回文子串，那题也是区间 DP 的经典题，但状态是二维的，因为回文需要知道左右边界；1567 只需要一维滚动变量，因为“长度”和“符号”都能靠迭代传到末尾。这两种题放在一起看很有意思：一个是在区间里判断性质，一个是在前缀上延续状态，DP 的维度设计完全由问题的连续性决定。如果你想加深对动态规划“状态设计”的理解，建议把这两题放到同一天刷，体会一下什么时候该开二维、什么时候一维就够。

5. 常见问题与调试技巧实录

5.1 最常见的三个翻车现场

翻车一：把“子数组”当成“子序列”。我见过不少解法，写着写着就变成了“跳着选负数”，比如对[1, -1, 2, -2]得出长度 4，因为[1, -1, 2, -2]里所有元素全选乘积为正？不对，连续地看[1, -1, 2, -2]乘积是 4，其实没问题。但如果你开始跳过中间的某个元素，比如对[1, -2, 3, -4]跳着选 1、-2、-4，那就不符合子数组定义。我们的 DP 转移里每个元素都是顺序连续的，不会出现跳过问题，但如果你自己实现自定义逻辑，就要时刻检查“是否保持了连续”。

翻车二：neg = neg + 1 if neg > 0 else 0这个判断写错。如果是正数x > 0，且之前没有负积子数组，那么当前元素接上以后乘积仍然是正的，不可能产生负积，所以neg必须是 0。如果你不加判断直接neg = neg + 1，在neg=0时会得到 1，这就错了，因为单个正数不能形成负积。

翻车三：零出现后忘记重置。这个属于“语义理解”问题。比如[1, -2, 0, 3]，如果不重置，可能会依赖前面的负积长度推出“以 3 结尾的负积长度”为 3，实际上 3 接上 0 那段乘积是 0，根本没有负积子数组通过 0 延续过来。所以遇到 0 清零是必须的，不能用什么偏移量绕过去。

5.2 调试手段：把状态数组打出来看

如果你用的是 DP 数组版本，调试时可以把pos和neg直接打印出来，对照手算结果。比如nums = [9, 10, 1, 0, 0, -9, -3]，最终输出应该是 3。打印出来的状态应该是：

nums: 9 10 1 0 0 -9 -3 pos: 1 2 3 0 0 0 1 neg: 0 0 0 0 0 1 2

看到-9那里，pos变成了 0，neg变成了 1，说明前面三段零把状态切断，-9只能自己开始。到了-3，neg是 2，表示[-9, -3]乘积为负？等一下，[-9, -3]乘积是 27 为正，那我这里打印是不是错了？

这段是我故意留的坑，咱们一起对着公式捋一遍：nums = [9, 10, 1, 0, 0, -9, -3]，到-9时，因为前一个是 0，状态是pos=0, neg=0，遇到负数，按公式pos = old_neg + 1 if old_neg > 0 else 0 = 0，neg = old_pos + 1 = 1，所以打印的pos=0, neg=1正确。到-3时，旧状态是pos=0, neg=1，遇到负数，pos = old_neg + 1 = 2，neg = old_pos + 1 = 1。所以正确的打印应该是pos: 1 2 3 0 0 0 2，neg: 0 0 0 0 0 1 1。我上面故意写错，想说明一件事：手推状态很容易出错，所以打印状态数组配合手算是排查 bug 最直接的方式，但前提是你要对自己手里的转移公式足够确信。

5.3 我的答题顺序建议：从“为什么”到“怎么写”

如果你在面试现场遇到这道题，我建议按这个顺序讲：

第一步，先讲“乘积为正”的数学条件：负号个数为偶数，且不能有零。这能让面试官知道你不是在背模板，而是理解题目的本质。

第二步，再引出“以 i 结尾”的一维 DP 状态，说明为什么要维护正、负两个长度：因为一个负数会翻转符号，单靠一个状态无法延续。

第三步，手写转移公式，重点强调三种情况：正数延申、负数翻转、零重置。

第四步，指出可以滚动变量优化到 O(1) 空间，然后写代码。

这套顺序下来，面试官一般会点头。如果面试官追问“能不能用双指针”，你可以回答说这题因为有零的断点，双指针不太好维护符号奇偶性，动态规划更自然。我自己的感觉是，面试中把“为什么这么设计状态”讲清楚，比默写出最优解更能加分。

写在最后：再分享一个刷题时的小技巧

这个题我后来复盘时发现，一个很实用的检查方法是：把每个子数组的“负号个数”当成核心指标。数量为偶数的连续段（中间没有 0）就是正积段，所以你其实可以把数组按 0 切成若干段，在每一段里数负号个数，奇数个负号就尝试去掉段首或段尾的某一个负数，看哪边剩下的长度更长。这个思路虽然不如 DP 通用，但做这道题时能帮你快速手算验证答案。我刷题时经常用它来预先推演结果，再跟 DP 输出对拍，一旦不一致，说明代码里某个边界处理漏了。希望这个技巧也能帮到你调试。