题目描述
思路解析动画文字版
记住「遇 0 清零、遇正 pos+1、遇负 正负交换」,pos 和 neg 一直在记两种乘积的最长结尾长度。
开局三个计数都为 0。从左往右逐个读:盯住 pos(正乘积最长结尾)和 neg(负乘积最长结尾)怎么随符号变化。
读到第 0 个是正数 1。正数不改变乘积符号:正的更正、负的更负,pos 能直接接着长。
更新:1 > 0 → pos = 旧pos+1 = 1;neg = 旧neg为0仍为 0。现在 pos=1,绿色就是当前「乘积为正」的最长结尾段。它超过了旧 ans,刷新 ans=1。
读到第 1 个是负数 -2。负数翻转符号:原来的正段会变负、原来的负段会变正,pos 和 neg 要互换着更新。
更新:pos=0(当前以这个数结尾还凑不出正乘积),neg=2。绿色暂时消失,等后面再出现负数把负段翻回正段。ans 仍是 1。
读到第 2 个是负数 -3。负数翻转符号:原来的正段会变负、原来的负段会变正,pos 和 neg 要互换着更新。
更新:-3 < 0 → pos = 旧neg+1 = 3;neg = 旧pos+1 = 1。现在 pos=3,绿色就是当前「乘积为正」的最长结尾段。它超过了旧 ans,刷新 ans=3。
读到第 3 个是正数 4。正数不改变乘积符号:正的更正、负的更负,pos 能直接接着长。
更新:4 > 0 → pos = 旧pos+1 = 4;neg = 旧neg+1 = 2。现在 pos=4,绿色就是当前「乘积为正」的最长结尾段。它超过了旧 ans,刷新 ans=4。
读到第 4 个是负数 -5。负数翻转符号:原来的正段会变负、原来的负段会变正,pos 和 neg 要互换着更新。
更新:-5 < 0 → pos = 旧neg+1 = 3;neg = 旧pos+1 = 5。现在 pos=3,绿色就是当前「乘积为正」的最长结尾段。还没超过 ans=4,保持。
读到第 5 个是 0。乘积一旦乘上 0 就变 0,绝不可能为正——它会把当前所有连胜清零。
更新:pos 和 neg 都清零(红色标出这个 0 是分界)。前面攒的连胜到此作废,下一段从 0 之后重新开始。ans 仍保留历史最大 4。
读到第 6 个是正数 6。正数不改变乘积符号:正的更正、负的更负,pos 能直接接着长。
更新:6 > 0 → pos = 旧pos+1 = 1;neg = 旧neg为0仍为 0。现在 pos=1,绿色就是当前「乘积为正」的最长结尾段。还没超过 ans=4,保持。
读到第 7 个是正数 7。正数不改变乘积符号:正的更正、负的更负,pos 能直接接着长。
更新:7 > 0 → pos = 旧pos+1 = 2;neg = 旧neg为0仍为 0。现在 pos=2,绿色就是当前「乘积为正」的最长结尾段。还没超过 ans=4,保持。
读到第 8 个是负数 -8。负数翻转符号:原来的正段会变负、原来的负段会变正,pos 和 neg 要互换着更新。
更新:pos=0(当前以这个数结尾还凑不出正乘积),neg=3。绿色暂时消失,等后面再出现负数把负段翻回正段。ans 仍是 4。
读到第 9 个是正数 9。正数不改变乘积符号:正的更正、负的更负,pos 能直接接着长。
更新:9 > 0 → pos = 旧pos+1 = 1;neg = 旧neg+1 = 4。现在 pos=1,绿色就是当前「乘积为正」的最长结尾段。还没超过 ans=4,保持。
扫完全程,绿色这 4 个 1、-2、-3、4 乘积为正(含 2 个负号,成对抵消),长度 4 就是答案。其余灰段要么含 0、要么负号是奇数个。
边界先想清:单负为 0、双负为正、0 处必清零。
两个追问,核心是认出「负号翻转 → 同时维护正负两态」这个母题。
参考代码
from typing import Listclass 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 ans复杂度
- 时间:O(n),从头到尾扫一遍
- 空间:O(1),只用 pos、neg、ans 三个变量
易错点
面试追问把动画讲成自己的话
追问不用 DP,能否用「记录负号位置」的思路?
追问这题和「乘积最大子数组 LC152」有何异同?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
使字符串平衡的最少删除次数
LeetCode 1653 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题