这道题我一开始做的时候以为就是个“最长连续子数组”的变体心想这不就是双指针扫一遍的事吗结果连着提交几次都没过才意识到问题出在“乘积为正数”这四个字上。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] 乘积为负长度 1pos[1] 1因为 [2] 乘积为正长度 1neg[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可能来自原来的neg0此时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] 输出: 30 左边是[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在neg0时会得到 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变成了 0neg变成了 1说明前面三段零把状态切断-9只能自己开始。到了-3neg是 2表示[-9, -3]乘积为负等一下[-9, -3]乘积是 27 为正那我这里打印是不是错了这段是我故意留的坑咱们一起对着公式捋一遍nums [9, 10, 1, 0, 0, -9, -3]到-9时因为前一个是 0状态是pos0, neg0遇到负数按公式pos old_neg 1 if old_neg 0 else 0 0neg old_pos 1 1所以打印的pos0, neg1正确。到-3时旧状态是pos0, neg1遇到负数pos old_neg 1 2neg old_pos 1 1。所以正确的打印应该是pos: 1 2 3 0 0 0 2neg: 0 0 0 0 0 1 1。我上面故意写错想说明一件事手推状态很容易出错所以打印状态数组配合手算是排查 bug 最直接的方式但前提是你要对自己手里的转移公式足够确信。5.3 我的答题顺序建议从“为什么”到“怎么写”如果你在面试现场遇到这道题我建议按这个顺序讲第一步先讲“乘积为正”的数学条件负号个数为偶数且不能有零。这能让面试官知道你不是在背模板而是理解题目的本质。第二步再引出“以 i 结尾”的一维 DP 状态说明为什么要维护正、负两个长度因为一个负数会翻转符号单靠一个状态无法延续。第三步手写转移公式重点强调三种情况正数延申、负数翻转、零重置。第四步指出可以滚动变量优化到 O(1) 空间然后写代码。这套顺序下来面试官一般会点头。如果面试官追问“能不能用双指针”你可以回答说这题因为有零的断点双指针不太好维护符号奇偶性动态规划更自然。我自己的感觉是面试中把“为什么这么设计状态”讲清楚比默写出最优解更能加分。写在最后再分享一个刷题时的小技巧这个题我后来复盘时发现一个很实用的检查方法是把每个子数组的“负号个数”当成核心指标。数量为偶数的连续段中间没有 0就是正积段所以你其实可以把数组按 0 切成若干段在每一段里数负号个数奇数个负号就尝试去掉段首或段尾的某一个负数看哪边剩下的长度更长。这个思路虽然不如 DP 通用但做这道题时能帮你快速手算验证答案。我刷题时经常用它来预先推演结果再跟 DP 输出对拍一旦不一致说明代码里某个边界处理漏了。希望这个技巧也能帮到你调试。