3202. 找出有效子序列的最大长度 II

发表于 分类于 阅读次数： Waline： 本文字数： 2.7k 阅读时长 ≈ 9 分钟

考点

  • 线性DP
  • 状态机DP
  • 数学

思路

解法一：按下标 + 固定 pair-sum 余数做 DP（f[i][m]）

建模

我们要找的是一个子序列 sub，使得对所有相邻对 (sub[t-1], sub[t])，都有 \[ (sub[t-1] + sub[t]) \bmod k = M \] 其中 \(M\) 是某个固定的余数（可以是 0..k-1 中任意值）。

对任意选出的子序列，如果它是合法的，那么它的所有相邻和模 k 值一定是同一个常数 \(M\)。因此我们可以按「最后一个元素的位置」和这个常数 \(M\) 来定义 DP。

定义状态：

  • 令 \(n = \text{nums.size()}\)；
  • 对每个下标 \(i \in [0, n-1]\)，每个余数 \(m \in [0, k-1]\)，定义

\[ f[i][m] = \text{以 nums[i] 作为最后一个元素，且所有相邻两数的和模 k 都等于 } m \text{ 的最长子序列长度} \]

注意：长度为 1 的子序列还没有相邻对，所以一开始我们可以把它当作“对所有 m 都是 1 的潜在起点”，在实现中初始化为 1。

答案则是： \[ \text{ans} = \max_{0 \le i < n} \max_{0 \le m < k} f[i][m] \]

状态转移方程

考虑把 nums[i] 作为某个合法子序列的最后一个元素，它前面可以接哪个位置 j 的元素？

  • 必须有 \(j < i\)，保证是子序列；
  • 如果我们要保持相邻和模 k 等于某个 m，那么必须满足

\[ (nums[j] + nums[i]) \bmod k = m \]

而以 nums[j] 结尾的前缀子序列若已经保证所有相邻和都是 m，则其长度是 \(f[j][m]\)。

因此，对于每一对 \(j < i\)，令 \[ m = (nums[j] + nums[i]) \bmod k \] 可以做转移： \[ f[i][m] = \max\bigl( f[i][m],\ f[j][m] + 1 \bigr) \] 也就是说：在所有能和 nums[i] 组成「相邻对余数为 m」的前一个位置 j 中，我们选择一个能给 f[i][m] 带来最大增长的。

边界条件：

  • 初始化时 f[i][m] = 1，表示只取单个元素 nums[i] 的长度为 1 的子序列（还没有真实的相邻对）。

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
31
32
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int n = nums.size();
        // f[i][m]：以 nums[i] 为最后一个元素，且所有相邻两数的和模 k 都等于 m 的最长子序列长度
        // 初始化为 1：单个 nums[i] 自成一个长度为 1 的子序列（目前还没有相邻对）
        vector<vector<int>> f(n, vector<int>(k, 1));

        int mx = 0;  // 记录全局最长长度

        // 枚举子序列最后一个位置 i
        for (int i = 0; i < n; ++i) {
            // 枚举前一个元素的位置 j（必须 j < i 才能形成子序列）
            for (int j = i - 1; j >= 0; --j) {
                // 当前要把 nums[j] 接到 nums[i] 前面作为相邻对 (nums[j], nums[i])
                // 这对相邻元素的和模 k 应该是 m
                int m = (nums[i] + nums[j]) % k;

                // 如果之前已经有一个以 j 结尾、相邻和都为 m 的子序列，
                // 那么现在在它后面再接上 nums[i]，长度增加 1
                // f[j][m]：以 nums[j] 结尾，pair-sum 余数为 m 的最长长度
                // f[i][m]：以 nums[i] 结尾，pair-sum 余数为 m 的最长长度
                f[i][m] = max(f[i][m], f[j][m] + 1);

                // 维护答案
                mx = max(mx, f[i][m]);
            }
        }

        return mx;
    }
};

解法二：在余数空间做 2 维 DP（交替余数模式 f[a][b]）

结构观察

先回顾题目的等价条件：对合法子序列 sub，对任意连续三项 \(a,b,c\)，有 \[ (a + b) \bmod k = (b + c) \bmod k \] 推出： \[ a \equiv c \pmod{k} \] 因此整个子序列在「模 k 余数」层面上的结构是：

  • 偶数位置的余数全都相等；
  • 奇数位置的余数全都相等。

也就是说：整个子序列的余数序列是形如 \[ x, y, x, y, x, y, \ldots \] 这样的交替模式（当 \(x = y\) 时则是常数序列）。

这提示我们，没必要显式记住 pair-sum 的模值 M；只要在余数空间中维护“交替的两种余数”就够了。

建模

把元素按模 k 的余数投影到 \([0, k-1]\) 上。对任意余数对 \((a,b)\)，定义 \[ f[a][b] = \text{在当前扫描到的位置为止，所有合法子序列中，最后一个元素模 k 余数为 } b，\text{且余数在 } a,b \text{ 之间交替的最长长度} \] 注意：

  • 当长度 ≥ 2 时，最后两项的余数一定分别是 \(a\) 和 \(b\)；
  • 当长度 = 1 时，可以认为这是某种退化情况（例如我们只记录了最后一个 b 元素，把 a 视作“未真正出现”的占位），但实现中只要统一用转移规则滚动即可。

状态转移方程

我们从左到右扫描原数组，对每个 nums[i]：

  • 设 \(x = nums[i] \bmod k\)，这是当前要加入的余数；
  • 我们希望它作为「交替模式中的一个 b」，接在某个以 a = x 或 a = 其他余数 结尾的序列后面。

这段代码是：

1
2
3
4
5
6
7
for (int i = 0; i < n; ++i) {
    int x = nums[i] % k;
    for (int r = 0; r < k; ++r) {
        f[r][x] = max(f[r][x], f[x][r] + 1);
        res = max(res, f[r][x]);
    }
}

对应到数学上：

  • 枚举所有可能的「前一个余数」\(r\)；
  • 如果之前存在一个余数交替为 \(x,r,x,r,\dots\)，且最后一个元素的余数是 \(r\) 的序列，它的长度为 \(f[x][r]\)；
  • 那么现在在它后面再加一个余数为 \(x\) 的元素，也就是把模式更新成 \(r,x,r,x,\dots\)，长度变为

\[ f[r][x] = \max\bigl(f[r][x],\ f[x][r] + 1\bigr) \]

这样一来，我们始终保持余数序列只在两个值之间交替，因此任意相邻对的和的余数都是固定的 \((a + b) \bmod k\)，从而保证了题目要求。

初始条件与答案

  • 数组 f 初始全为 0，表示尚未构造出任何序列；
  • 每来一个元素，我们根据公式更新；一旦某个 f[r][x] 变为 1，说明我们至少以这个余数作为末尾构造出了一条长度为 1 的基础链；
  • 全程维护 res = max(res, f[r][x]) 即可。

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
31
32
33
34
35
36
37
38
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        // f[a][b]：在处理到当前位置为止，
        // 余数序列在 a 与 b 之间交替，且最后一个元素的余数为 b 的
        // 合法子序列的最大长度
        //
        // 注意：当长度 >= 2 时，余数模式就是 a,b,a,b,... 或 b,a,b,a,...
        //       这种交替结构保证了所有相邻两数的和模 k 相等。
        static int f[1005][1005];
        int n = nums.size();

        // 静态数组局部声明时会被自动置 0，这里等价于 memset(f,0,...)
        // 如担心可自行加一行 memset(f,0,sizeof(f));

        int res = 0;  // 全局答案

        for (int i = 0; i < n; ++i) {
            int x = nums[i] % k;  // 当前元素的余数

            // 枚举“前一个余数” r，把当前 x 接在末尾
            for (int r = 0; r < k; ++r) {
                // 之前如果存在一个模式为 (x,r,x,r,...)，最后一个余数为 r 的序列，
                // 其长度是 f[x][r]。
                //
                // 现在在它后面再接一个余数为 x 的元素，
                // 模式就变为 (r,x,r,x,...)，最后一个余数为 x，
                // 对应状态 f[r][x]，长度增加 1。
                f[r][x] = max(f[r][x], f[x][r] + 1);

                // 更新全局最大长度
                res = max(res, f[r][x]);
            }
        }

        return res;
    }
};

解法三：固定 pair-sum 余数 M，在余数空间做一维 DP（f[x]）

这一份就是你前面看到的「只用一维」的写法，只不过这里是外层枚举 pair-sum 的余数 M，再在余数空间做 DP。

再次利用“交替两种余数”的结构

结合前面的结论：如果一个子序列是合法的，则存在某个 \(M \in [0, k-1]\)，对所有相邻对 \((a,b)\) 有 \[ (a + b) \bmod k = M \] 于是对于每一对相邻元素的余数 \(ra, rb\)，必须满足： \[ ra + rb \equiv M \pmod{k} \] 也就是： \[ rb \equiv M - ra \pmod{k} \] 因此如果我们事先固定某个 M，那么：

  • 一条 pair-sum 余数为 M 的合法子序列，在“余数层面”上必须满足：
    • 若当前最后一个元素的余数是 \(x\)，则前一个元素的余数必须是 \(y = (M - x) \bmod k\)。

这就给出了一种天然的 DP 方式。

建模（固定 M 的一维 DP）

我们对每个可能的 \(M \in [0, k-1]\) 分别做一遍 DP。 在固定某个 M 时，定义： \[ f[x] = \text{在当前扫描到的位置为止，所有合法子序列中，最后一个元素的余数为 } x， \text{并且所有相邻和模 k 都等于 M 的最长长度} \] 然后从左到右扫描原数组的每一个数 nums[i]：

  • 设 \(x = nums[i] \bmod k\)，这是新来的末尾余数；
  • 如果我们要保持 pair-sum 余数为 M，则前一个余数必须是

\[ y = (M - x) \bmod k \]

所以可以从所有「以余数 y 结尾」的合法子序列转移过来： \[ f[x] = \max\bigl( f[x],\ f[y] + 1 \bigr) \] 实现里，外层枚举 M，用代码变量 r 表示。

状态转移方程（代码对应）

对固定的 r（数学上的 M），对每个 x = nums[i] % k，令 \[ y = (r - x + k) \bmod k \] 转移为： \[ f[x] = \max\bigl( f[x],\ f[y] + 1 \bigr) \] 同时维护全局 res 最大值。

初始条件与答案

  • 对每个固定的 r，我们都重新 memset(f, 0, ...)；
  • f[x] = 0 表示尚未有以余数 x 结尾、pair-sum 余数为 r 的子序列；
  • 一旦遇到一个新元素余数为 x，就可以把它视为单独一条长度为 1 的候选链（通过 f[y] + 1 自然生成），再逐步在扫描过程中向后扩展；
  • 全程维护 res 即可。

复杂度为 \(O(nk)\)：外层枚举 k 个 M，内层对每个 M 扫一遍长度为 n 的数组，转移在余数空间是一维的。

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
31
32
33
34
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int n = nums.size();
        int f[1005];   // f[x]：在当前固定的 pair-sum 余数 r 下，
                       // 以余数 x 结尾、且所有相邻和模 k 都等于 r 的
                       // 合法子序列的最大长度
        int res = 0;   // 全局答案

        // 枚举 pair-sum 的目标余数 r = M
        for (int r = 0; r < k; ++r) {
            // 每个 r 都是一次独立的 DP，f 需要从 0 开始
            memset(f, 0, sizeof(f));

            // 扫描整个数组
            for (int x : nums) {
                x %= k;  // 当前元素的余数 x

                // 若所有相邻对的和模 k 都要等于 r，
                // 且当前末尾余数为 x，那么前一个元素的余数
                // 必须是 y = (r - x) mod k
                int y = (r - x + k) % k;

                // 从以余数 y 结尾的最佳序列转移而来，再接上当前 x
                f[x] = max(f[x], f[y] + 1);

                // 更新全局答案
                res = max(res, f[x]);
            }
        }

        return res;
    }
};