LeetCode 1567. 乘积为正数的最长子数组长度

2026-02-11 HGNULB 约 10 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1567. 乘积为正数的最长子数组长度

题意分析

给定整数数组 nums，求最长的连续子数组，使其所有元素之积为正数，返回这个长度。

「乘积为正」这个条件看似要算乘积，其实只关心符号，而符号只由两件事决定：区间内有没有 $0$，以及负数的个数是奇数还是偶数。元素的绝对值大小完全无关，$nums[i]$ 可以到 $10^9$ 而不必担心乘积溢出——因为根本不需要真的相乘。

$0$ 是硬边界：任何包含 $0$ 的子数组乘积都是 $0$，既不正也不负。所以 $0$ 把数组切成若干互不相干的段，答案只能在某一段内部产生。

数据范围 $n \le 10^5$ 指向 $O(n)$ 或 $O(n \log n)$。枚举所有子数组是 $O(n^2)$ 对起点终点，配合前缀符号还能做到 $O(n^2)$ 判定，仍然超时，必须一趟扫描解决。

边界要盯住三处：整段全是正数时答案就是段长；某段负数个数为奇数时，必须舍弃一端的某个负数，答案不是整段；数组里可能全是 $0$，此时答案为 $0$（空子数组不计，题目要求的是有元素的子数组）。

解法：动态规划状态转移

核心思路

暴力做法是枚举左右端点，维护区间内负数个数与是否含 $0$，$O(n^2)$ 判定。瓶颈在于：同一个右端点的所有左端点被独立地考察了一遍，而它们之间存在明显的递推关系——右端点右移一格时，「以它结尾的合法区间」可以由「以前一格结尾的合法区间」直接延伸得到。

于是转向以「结尾位置」为维度的动态规划。但只记「以 $i$ 结尾且乘积为正的最长长度」是不够的：当下一个元素是负数时，正积会变负，而负积区间反而会因为再乘一个负数变正。也就是说，负积的信息是有价值的，必须一起维护。这正是本题的核心——状态要成对定义。

显式写出两个状态：pos 表示以当前元素结尾、乘积为正的最长子数组长度；neg 表示以当前元素结尾、乘积为负的最长子数组长度。约定值为 $0$ 表示「不存在这样的子数组」，因为合法子数组至少含一个元素、长度至少为 $1$，所以 $0$ 是一个安全的哨兵，不会与真实长度混淆。

转移按当前元素 $x$ 的符号分三支：

$x > 0$ 时，乘上一个正数不改变符号。以它结尾的正积区间 = 前一位的正积区间延长一格（前一位的正积区间为空时，就是它自己），所以 pos = pos + 1——注意由于 pos = 0 表示不存在，加一后恰好得到「只含自己」的长度 $1$，这个哨兵设计让转移不需要特判。负积区间则只能由前一位的负积区间延长，前一位没有负积区间时它也造不出负积，所以要写成「neg > 0 才加一，否则保持 $0$」。

$x < 0$ 时，符号翻转。新的正积区间必须由前一位的负积区间延长而来，同样地前一位无负积时新的正积就不存在（不能写成 $0 + 1$，那会凭空造出一个长度 $1$ 的正积区间，而单个负数的积是负的）；新的负积区间由前一位的正积区间延长而来，前一位正积为 $0$ 时加一得到 $1$，恰好表示「只含这个负数自己」，语义正确。两条式子都读旧值，所以必须先算进临时变量再一起赋回。

$x = 0$ 时，任何跨越它的区间都作废，pos 与 neg 同时清零，相当于从下一个位置重新开始。这正是「$0$ 切分数组」的落实。

全程的不变量是：处理完下标 $i$ 后，pos 与 neg 分别是以 $i$ 结尾的正积、负积最长长度，$0$ 表示不存在。每一步用 pos 更新全局答案 best 即可。

解题步骤

初始化 pos = 0、neg = 0、best = 0。三个 $0$ 各有含义：前两个表示「在第一个元素之前，不存在任何以其结尾的区间」，第三个是答案下界（全 $0$ 数组时答案确实为 $0$）。

单趟从左到右遍历。状态只依赖前一个位置，所以正向一次扫描即可，不需要数组存历史。

$x > 0$ 分支：pos = pos + 1；neg 仅在原本大于 $0$ 时加一。前者能无条件加一，是因为 pos = 0 加一后正好是「区间只含 $x$ 自己」这个真实存在的正积区间；后者不能无条件加一，因为不存在负积前缀时，乘一个正数仍造不出负积。

$x < 0$ 分支：新 pos 在旧 neg > 0 时取 neg + 1、否则取 $0$；新 neg 恒取 pos + 1。前者的条件判断同理——负负得正需要真的有一个负积前缀；后者可以无条件加一，因为旧 pos = 0 时加一表示「区间只含这个负数」，它的积确实是负的。

$x < 0$ 分支必须用临时变量再统一赋回。两条式子交叉读取对方的旧值，就地更新会让第二条读到已被覆盖的新值。

$x = 0$ 分支：两个状态一起清零。含 $0$ 的区间既非正也非负，前面积累的一切在此中断。

每轮末尾执行 best = max(best, pos)。答案只关心正积，所以只用 pos 更新；放在分支之外统一做，能覆盖三种情况（$x = 0$ 时 pos 为 $0$，不会污染 best）。

返回 best。

以 nums = [1, -2, -3, 4] 走一遍：

初始 pos = 0, neg = 0, best = 0。
$x = 1$（正）：pos = 0 + 1 = 1；neg 原为 $0$，保持 $0$。best = 1。此刻以下标 0 结尾的正积区间是 [1]，长度 1；没有负积区间。
$x = -2$（负）：旧 neg = 0 所以新 pos = 0；新 neg = pos + 1 = 2。赋回得 pos = 0, neg = 2。best 仍为 $1$。以下标 1 结尾：负积区间是 [1, -2]，长度 2；没有正积区间（[-2] 是负的，[1,-2] 也是负的）。
$x = -3$（负）：旧 neg = 2 > 0，新 pos = 2 + 1 = 3；新 neg = pos + 1 = 0 + 1 = 1。赋回得 pos = 3, neg = 1。best = 3。以下标 2 结尾：正积区间 [1, -2, -3] 长度 3；负积区间只有 [-3] 长度 1——正是因为旧 pos 为 $0$，加一得到「只含自己」。
$x = 4$（正）：pos = 3 + 1 = 4；neg = 1 > 0 所以 neg = 2。best = 4。
返回 $4$，对应整个数组，其中有两个负数（偶数个），乘积为正。

再看含 $0$ 的用例 nums = [0, 1, -2, -3, -4]：$x = 0$ 时两状态清零；随后 1 使 pos = 1；-2 使 pos = 0, neg = 2；-3 使 pos = 3, neg = 1；-4 使 pos = neg + 1 = 2（由 [-3, -4] 得来）、neg = 3 + 1 = 4。best 停在 $3$。答案 $3$ 对应 [1, -2, -3]——第四个负数把整段的负数个数变成奇数，只能退而求其次。这一步清楚展示了 neg 存在的价值：没有它，-4 之后就找不到任何正积区间了。

代码实现

class Solution {
    public int getMaxLen(int[] nums) {
        int pos = 0;
        int neg = 0;
        int best = 0;

        for (int x : nums) {
            if (x > 0) {
                pos = pos + 1;
                if (neg > 0) {
                    neg = neg + 1;
                }
            } else if (x < 0) {
                int newPos = 0;
                if (neg > 0) {
                    newPos = neg + 1;
                }
                int newNeg = pos + 1;
                pos = newPos;
                neg = newNeg;
            } else {
                pos = 0;
                neg = 0;
            }
            best = Math.max(best, pos);
        }

        return best;
    }
}

func getMaxLen(nums []int) int {
    pos, neg := 0, 0
    best := 0

    for _, x := range nums {
        if x > 0 {
            pos = pos + 1
            if neg == 0 {
                neg = 0
            } else {
                neg = neg + 1
            }
        } else if x < 0 {
            newPos := 0
            if neg != 0 {
                newPos = neg + 1
            }
            newNeg := pos + 1
            pos, neg = newPos, newNeg
        } else {
            pos, neg = 0, 0
        }

        if pos > best {
            best = pos
        }
    }

    return best
}

复杂度分析

时间复杂度：$O(n)$。每个元素只被访问一次，循环体内是常数次比较与加法，没有嵌套循环，也不需要预处理前缀信息。

空间复杂度：$O(1)$。虽然是动态规划，但状态只依赖前一个位置，用 pos、neg 两个滚动变量即可，不必开长度 $n$ 的数组；这是「一维 DP 且转移只跨一格」时的标准压缩。

关键点总结

当最优解可能由「当前看起来更差的状态」转化而来时，状态就必须成对（或成组）维护。本题正积会被一个负数变负、负积也会被另一个负数变正，所以 pos 与 neg 缺一不可；同样的道理也支配着「乘积最大子数组」里同时记最大值和最小值。

用 $0$ 当「不存在」的哨兵时，要逐条检查转移式在哨兵上的行为是否恰好正确。本题 pos + 1 在哨兵上恰好表示「只含自己」而语义成立，neg + 1 却不成立，必须加条件判断——两条式子长得像但待遇不同，这是最容易写错的地方。

乘积类问题先做符号约化：只关心正负时，把「乘法」换成「负号个数的奇偶」，既避免溢出也简化状态。

$0$ 是天然的分割点，遇到它就重置状态；这种「重置型 DP」在「最大连续 1 的个数」「和为正的最长段」等题里反复出现。

面试视角：面试官会先问「只记 pos 行不行」——要能立刻举出 [1, -2, -3] 说明不行；再问「为什么 $x<0$ 时新 pos 要判条件而新 neg 不用」——要能从哨兵语义上解释；最后可能追问「不用 DP 还能怎么做」，可以答按 $0$ 分段后，段内若负数个数为偶则取整段，为奇则在「去掉第一个负数及其左侧」与「去掉最后一个负数及其右侧」两者中取长，这是等价的贪心解法。

易错点总结

$x > 0$ 时无条件写 neg = neg + 1：nums = [1, 2] 时第二步 neg 变成 $1$，凭空造出一个不存在的负积区间；后续若出现负数，pos 会由这个假 neg 推出错误的长度。

$x < 0$ 时无条件写 pos = neg + 1：nums = [-1] 时 pos 变成 $1$，best 返回 $1$，而单个 $-1$ 的积是负数，正确答案是 $0$。

$x < 0$ 分支就地更新不用临时变量：先写 pos = neg + 1 再写 neg = pos + 1，nums = [1, -2] 会得到 pos = 0（旧 neg 为 0）后 neg = 1，看似巧合正确，但 nums = [1, -2, -3] 处第三步会用刚改过的 pos 算 neg，得到 neg = 4 这种超过实际长度的值。

遇到 $0$ 只清 pos 不清 neg：nums = [-1, 0, -1] 时第三步会用残留的 neg = 1 算出 pos = 2，返回 $2$，而跨越 $0$ 的区间乘积为 $0$，正确答案是 $0$。

用 best = max(best, neg) 或同时用两者更新：nums = [-1, -2, -3] 时 neg 一度为 $3$，会返回 $3$，而三个负数乘积为负，正确答案是 $2$。

真的去累乘判断符号：nums = [10^9, 10^9] 时乘积溢出 int（甚至 long），符号判断完全失真。

把「子数组」理解成「子序列」：nums = [-1, 2, -1] 若允许跳过中间元素会返回 $2$（取两个 $-1$），本题要求连续，正确答案是 $3$。

best 初始化为 $1$ 或 nums.length：nums = [0] 会返回 $1$，正确答案是 $0$；nums = [-1] 同样返回 $1$ 而非 $0$。

把 $x = 0$ 的分支并进 $x < 0$（用 else 而非 else if x < 0）：nums = [0] 时会按负数处理，neg 变成 $1$，后续元素据此推出错误的 pos。

每轮忘记更新 best，只在循环结束后取一次 pos：nums = [1, 2, -3] 结束时 pos 为 $0$，返回 $0$，正确答案是 $2$。

相似题目

题目	难度	考察点
152. 乘积最大子数组	中等	同样成对维护最大与最小乘积，但求的是乘积数值而非长度，需处理数值而非符号
53. 最大子数组和	中等	一维滚动 DP 的入门形态，只需单状态，因为加法不会把大值变小值
485. 最大连续 1 的个数	简单	同为「遇到分隔元素就重置」的扫描，无需第二个状态
487. 最大连续1的个数 II	中等	允许翻转一个 $0$，状态多一维「是否已用掉翻转机会」，与本题的双状态思路同源
525. 连续数组	中等	求 0/1 数量相等的最长子数组，靠前缀和首次出现位置而非逐位 DP
674. 最长连续递增序列	简单	同为「以当前位置结尾的最长长度」，条件断裂时重置为 1 而非 0
560. 和为 K 的子数组	中等	统计数量而非求最长，用前缀和加哈希表，允许负数导致无法滑窗
926. 将字符串翻转到单调递增	中等	同为两状态滚动 DP，状态是「当前位翻成 0 还是 1」的最小代价