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

约 6 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 虾皮
标签
数组 动态规划 贪心

题目描述

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

image-20260928230602791

image-20260928230602793

题意分析

求乘积为正数的最长连续子数组长度。数值本身并不影响目标，只需要知道元素的正负与是否为零；直接计算乘积反而可能溢出。

可以从左到右维护以当前位置结尾的最长正乘积、负乘积片段。负片段虽然暂时不能作为答案，遇到下一个负数后却能变成正片段，因此也必须保留。

解法：动态规划状态转移

核心思路

[!blue]

pos 表示以当前处理位置结尾、乘积为正的最长长度，neg 表示同样结尾、乘积为负的最长长度。长度为 0 表示不存在这种片段。每轮读取新元素 x 时，旧状态对应前一个位置。

若 x > 0，乘积符号不变。旧正片段可以延长，pos = oldPos+1；即使旧正片段不存在，当前正数单独就能形成长度 1。负片段只能从已有负片段延长，因此旧 neg > 0 时才加一，否则仍为 0。

若 x < 0，乘积符号交换。新的正片段必须由旧负片段接上当前负数得到，所以旧 neg > 0 时新正长度是 oldNeg+1，否则不存在。新的负片段可以由旧正片段延长，长度为 oldPos+1；旧正片段不存在时，这个式子得到 1，表示当前负数单独成段。两个新值都必须读取旧状态，再一起赋值。

若 x == 0，任何跨过它的片段乘积都为零，不属于正或负状态，因此将 pos、neg 一起清空，之后从新位置重新开始。

这些转移覆盖了单个元素成段和延长前一位置片段的所有可能。同一符号只保留最长长度就足够，因为接上同一个新元素时，它们的符号变化相同，长度都只增加一，较短片段不会反而更优。每轮用 pos 更新全局最大值 best，最终就覆盖所有可能的结束位置。

解题步骤

  1. 初始化 pos = 0、neg = 0、best = 0。
  2. 当前元素为正数时，正长度加一；只有负长度已经存在时，才将负长度加一。
  3. 当前元素为负数时，先由两个旧状态计算新正、新负长度，再同时替换。
  4. 当前元素为零时清空两种结尾状态，但不清空全局答案。
  5. 每轮更新 best = max(best, pos)，遍历结束后返回 best。若始终没有正乘积片段，结果自然为 0。

代码实现

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 = 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)$。只保存正负长度、临时新状态和全局最大长度。

关键点总结

[!green]

  • 状态要求片段恰好在当前位置结束，全局答案再比较所有结束位置。
  • 符号相同的候选只保留最长长度，之后的统一延长不会改变长短关系。
  • 正数保持符号，负数交换符号，零切断所有跨越它的片段。
  • 0 表示状态不存在，不能让不存在的负片段直接加一变成正片段。

易错点总结

[!yellow]

  • 只保留正片段，会漏掉旧负片段乘上负数后形成的更长答案。
  • 负数分支先覆盖 pos 再计算 neg，会把新旧状态混用。
  • 旧负长度为 0 时仍计算 newPos = neg+1，会把当前单个负数误当作正乘积。
  • 遇到零不重置状态，会错误连接零两侧的子数组；同时把 best 清零，又会丢掉之前找到的答案。
  • 直接连乘数值没有必要，长子数组的乘积很容易溢出，符号和长度已经足够。

相似题目

题目 难度 关联与区别
152. 乘积最大子数组 中等 原题最大化乘积数值，本题只关心乘积符号，可维护正负两种最长长度而不实际相乘。
525. 连续数组 中等 同样可用前缀状态寻找最长匹配区间，本题状态是负数个数奇偶，并在0处切断。
53. 最大子数组和 中等 维护以当前位置结尾的最优连续区间；本题只维护正负乘积对应的最长长度，该题记录最大连续和。
918. 环形子数组的最大和 中等 维护以当前位置结尾的最优连续区间；本题只维护正负乘积对应的最长长度，该题同时计算最小区间和处理首尾相接。
1186. 删除一次得到子数组最大和 中等 维护以当前位置结尾的最优连续区间；本题只维护正负乘积对应的最长长度，该题增加已经删除一次的状态。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/78032657
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！