LeetCode 1567中等DP
乘积为正数的最长子数组长度 图解题解
这道题到底在问什么
给定整数数组 nums，返回「乘积为正数」的最长连续子数组的长度。乘积为 0 不算正。
- 输入
- nums=[1,-2,-3,4]
- 输出
- 4 （整段乘积 = 正，负号成对抵消）
最优解：一步一步想明白
- 3记住「遇 0 清零、遇正 pos+1、遇负 正负交换」，pos 和 neg 一直在记两种乘积的最长结尾长度。
- 4开局三个计数都为 0。从左往右逐个读：盯住 pos（正乘积最长结尾）和 neg（负乘积最长结尾）怎么随符号变化。
- 5读到第 0 个是正数 1。正数不改变乘积符号：正的更正、负的更负，pos 能直接接着长。
- 6更新：1 > 0 → pos = 旧pos+1 = 1；neg = 旧neg为0仍为 0。现在 pos=1，绿色就是当前「乘积为正」的最长结尾段。它超过了旧 ans，刷新 ans=1。
- 7读到第 1 个是负数 -2。负数翻转符号：原来的正段会变负、原来的负段会变正，pos 和 neg 要互换着更新。
- 8更新：pos=0（当前以这个数结尾还凑不出正乘积），neg=2。绿色暂时消失，等后面再出现负数把负段翻回正段。ans 仍是 1。
- 9读到第 2 个是负数 -3。负数翻转符号：原来的正段会变负、原来的负段会变正，pos 和 neg 要互换着更新。
- 10更新：-3 < 0 → pos = 旧neg+1 = 3；neg = 旧pos+1 = 1。现在 pos=3，绿色就是当前「乘积为正」的最长结尾段。它超过了旧 ans，刷新 ans=3。
- 11读到第 3 个是正数 4。正数不改变乘积符号：正的更正、负的更负，pos 能直接接着长。
- 12更新：4 > 0 → pos = 旧pos+1 = 4；neg = 旧neg+1 = 2。现在 pos=4，绿色就是当前「乘积为正」的最长结尾段。它超过了旧 ans，刷新 ans=4。
- 13读到第 4 个是负数 -5。负数翻转符号：原来的正段会变负、原来的负段会变正，pos 和 neg 要互换着更新。
- 14更新：-5 < 0 → pos = 旧neg+1 = 3；neg = 旧pos+1 = 5。现在 pos=3，绿色就是当前「乘积为正」的最长结尾段。还没超过 ans=4，保持。
- 15读到第 5 个是 0。乘积一旦乘上 0 就变 0，绝不可能为正——它会把当前所有连胜清零。
- 16更新：pos 和 neg 都清零（红色标出这个 0 是分界）。前面攒的连胜到此作废，下一段从 0 之后重新开始。ans 仍保留历史最大 4。
- 17读到第 6 个是正数 6。正数不改变乘积符号：正的更正、负的更负，pos 能直接接着长。
- 18更新：6 > 0 → pos = 旧pos+1 = 1；neg = 旧neg为0仍为 0。现在 pos=1，绿色就是当前「乘积为正」的最长结尾段。还没超过 ans=4，保持。
- 19读到第 7 个是正数 7。正数不改变乘积符号：正的更正、负的更负，pos 能直接接着长。
- 20更新：7 > 0 → pos = 旧pos+1 = 2；neg = 旧neg为0仍为 0。现在 pos=2，绿色就是当前「乘积为正」的最长结尾段。还没超过 ans=4，保持。
- 21读到第 8 个是负数 -8。负数翻转符号：原来的正段会变负、原来的负段会变正，pos 和 neg 要互换着更新。
- 22更新：pos=0（当前以这个数结尾还凑不出正乘积），neg=3。绿色暂时消失，等后面再出现负数把负段翻回正段。ans 仍是 4。
- 23读到第 9 个是正数 9。正数不改变乘积符号：正的更正、负的更负，pos 能直接接着长。
- 24更新：9 > 0 → pos = 旧pos+1 = 1；neg = 旧neg+1 = 4。现在 pos=1，绿色就是当前「乘积为正」的最长结尾段。还没超过 ans=4，保持。
- 25扫完全程，绿色这 4 个 1、-2、-3、4 乘积为正（含 2 个负号，成对抵消），长度 4 就是答案。其余灰段要么含 0、要么负号是奇数个。
⚠️ 容易写错的地方
✗ 错：遇负数时先更新 pos 再用旧 pos 算 neg
✓ 对：必须用「同一时刻的旧 pos、旧 neg」同时算新值
先改 pos 会污染算 neg 用的旧 pos，要么交换、要么用临时变量
✗ 错：neg 从 0 直接 +1
✓ 对：neg 只有原来 > 0 才能延长，否则保持 0
没有负段可接时，硬加会凭空造出不存在的负乘积段
✗ 错：把 0 也算进正乘积
✓ 对：遇 0 一律清零
乘积含 0 就是 0，不是正数
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def getMaxLen(self, nums: List[int]) -> int:
pos = neg = ans = 0
for x in nums:
if x == 0:
pos = neg = 0
elif x > 0:
pos += 1
neg = neg + 1 if neg else 0
else:
pos, neg = (neg + 1 if neg else 0), pos + 1
ans = max(ans, pos)
return ansC++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int pos = 0, neg = 0, ans = 0;
for (int x : nums) {
if (x == 0) pos = neg = 0;
else if (x > 0) { ++pos; neg = neg ? neg + 1 : 0; }
else { int oldPos = pos; pos = neg ? neg + 1 : 0; neg = oldPos + 1; }
ans = max(ans, pos);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int getMaxLen(int[] nums) {
int pos = 0, neg = 0, ans = 0;
for (int x : nums) {
if (x == 0) { pos = 0; neg = 0; }
else if (x > 0) { pos++; neg = neg == 0 ? 0 : neg + 1; }
else { int oldPos = pos; pos = neg == 0 ? 0 : neg + 1; neg = oldPos + 1; }
ans = Math.max(ans, pos);
}
return ans;
}
}复杂度
时间
O(n)
从头到尾扫一遍
空间
O(1)
只用 pos、neg、ans 三个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 乘积为正数的最长子数组长度 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不用 DP，能否用「记录负号位置」的思路？+
可以。以每个 0 分段，在每段里数负数个数：偶数个则整段都正，长度即段长；奇数个则去掉「第一个负号之前」或「最后一个负号之后」较短的一截，取较长者。两种思路等价，DP 写起来更短、更不易错。
这题和「乘积最大子数组 LC152」有何异同？+
都靠「同时维护正负两个极值/长度」来应对负号翻转。LC152 维护的是最大、最小乘积值，本题维护的是正、负乘积的最长长度，套路同源。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 乘积为正数的最长子数组长度 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。