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

发表于 分类于 阅读次数： Waline： 本文字数： 753 阅读时长 ≈ 3 分钟

考点

  • 状态机DP

一、题目简述

给定一个整数数组 nums，求乘积为正数的最长连续子数组长度。

需要注意三种数值类型对乘积符号的影响：

  • 正数：不改变符号
  • 负数：翻转符号
  • 0：直接中断子数组

二、状态定义（State Definition）

定义二维 DP： \[ f[i][0] = \text{以第 } i \text{ 个元素结尾，乘积为正的最长连续子数组长度} \] 这里的关键点是：

  • 一定是“以 \(i\) 结尾”
  • 必须包含 nums[i]
  • 所有不以 i 结尾的子数组，由最终答案统一取最大值

三、初始值（Initialization）

由于数组从 i = 1 开始计算： \[ f[0][0] = f[0][1] = 0 \] 表示在没有任何元素时，不存在合法子数组。

当遇到：

  • 正数 → 可单独形成正积子数组
  • 负数 → 可单独形成负积子数组
  • 0 → 全部清零（子数组被截断）

这些都在状态转移时隐式完成初始化。

四、状态转移方程（Transition Equations）

设当前元素： \[ x = nums[i] \]

✅ 情况一：当前元素为正数 \(x > 0\)

  • 正 × 正 = 正
  • 负 × 正 = 负

状态转移为： \[ f[i][0] = \max(1, f[i-1][0] + 1) \]

✅ 情况二：当前元素为负数 \(x < 0\)

  • 正 × 负 = 负
  • 负 × 负 = 正

状态转移为： \[ f[i][1] = \max(1, f[i-1][0] + 1) \]

✅ 情况三：当前元素为 0

由于 0 会直接使乘积变为 0，不可能为正或负，因此： \[ f[i][0] = 0,\quad f[i][1] = 0 \] 相当于子数组在此被强制截断。

五、最终答案（Result Extraction）

由于最长子数组不一定以最后一个元素结尾，因此答案应为： \[ \text{ans} = \max_{1 \le i \le n} f[i][0] \] 即：

1
2
3
int res = 0;
for (int i = 1; i <= nums.size(); ++i)
    res = max(res, f[i][0]);

六、完整 AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    static const int maxn = 1e5 + 5;
    int getMaxLen(vector<int>& nums) {
        int f[maxn][2];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= nums.size(); ++i) {
            int x = nums[i - 1];
            if (x > 0) {
                f[i][0] = 1;
                if (f[i - 1][0])
                    f[i][0] = max(1, f[i - 1][0] + 1);
                if (f[i - 1][1])
                    f[i][1] = max(0, f[i - 1][1] + 1);
            } else if (x < 0) {
                f[i][1] = 1;
                if (f[i - 1][0])
                    f[i][1] = max(1, f[i - 1][0] + 1);
                if (f[i - 1][1])
                    f[i][0] = max(0, f[i - 1][1] + 1);
            } else {
                f[i][1] = f[i][0] = 0;
            }
        }
        int res = 0;
        for (int i = 1; i <= nums.size(); ++i)
            res = max(res, f[i][0]);
        return res;
    }
};

当然也可以滚动数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    static const int maxn = 1e5 + 5;
    int getMaxLen(vector<int>& nums) {
        int res = 0, a = 0, b = 0;
        for (int i = 1; i <= nums.size(); ++i) {
            int x = nums[i - 1], ta = 0, tb = 0;
            if (x > 0) {
                ta = 1;
                if (a)
                    ta = max(1, a + 1);
                if (b)
                    tb = max(0, b + 1);
            } else if (x < 0) {
                tb = 1;
                if (a)
                    tb = max(1, a + 1);
                if (b)
                    ta = max(0, b + 1);
            }
            a = ta, b = tb;
            res = max(res, a);
        }
        return res;
    }
};

七、补充说明（用于讲解时强调）

  • 本题本质是符号状态机 DP
  • 负数的作用是：正负互换
  • 0 的作用是：状态清零，强制断开
  • f[i][0] 才是合法答案来源，因为题目要求乘积为正