1218. 最长定差子序列

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

考点

  • 线性DP

思路

一、问题描述

给定一个整数数组 \[ \texttt{arr} = [a_1, a_2, \dots, a_n] \] 以及一个整数差值 \[ d = \texttt{difference} \] 要求从 arr 中选取一个子序列（不要求连续），使得该子序列中任意相邻两个元素满足： \[ a_{i_{k+1}} - a_{i_k} = d \] 目标是求这样的子序列的最大长度。

二、问题建模

2.1 子序列的结构特征

对于一个满足条件的子序列： \[ x_1, x_2, \dots, x_k \] 必然有： \[ x_{j+1} = x_j + d \] 因此，整个子序列的值是严格按固定差值递推的。 这意味着：

一个以数值 \(x\) 结尾的最优子序列，其前一个元素一定是 \(x - d\)。

2.2 动态规划状态定义

定义状态： \[ f(x) = \text{以数值 } x \text{ 作为结尾的最长定差子序列长度} \] 注意，这里的状态是按“数值”而非“下标”定义的，这是本题的关键建模点。

三、状态转移方程

3.1 转移推导

如果当前处理到的数组元素为 \(x\)，那么：

  • 若此前存在以 \(x - d\) 结尾的子序列，其长度为 \(f(x - d)\)
  • 则可以将 \(x\) 接在该子序列后面

因此状态转移为： \[ f(x) = f(x - d) + 1 \] 如果此前从未出现过 \(x - d\)，则视为： \[ f(x - d) = 0 \Rightarrow f(x) = 1 \]

3.2 初始化

在算法开始时： \[ f(x) = 0 \quad \forall x \] 表示尚未形成任何子序列。

3.3 答案提取

最终答案为所有状态中的最大值： \[ \max_x f(x) \]

四、值域优化与数组化实现

4.1 值域分析

根据题目约束： \[ -10^4 \le arr[i],\ difference \le 10^4 \] 因此所有可能访问到的数值： \[ x,\ x - d \in [-2\times10^4,\ 2\times10^4] \] 值域大小是常数级别的。

4.2 平移映射

为了使用数组代替哈希表，引入一个偏移量： \[ \texttt{OFFSET} = 20000 \] 将数值 \(x\) 映射为数组下标： \[ \text{index}(x) = x + \texttt{OFFSET} \] 这样即可保证所有访问都在合法数组范围内。

五、算法流程总结

  1. 使用数组 f[] 记录状态 \(f(x)\)

  2. 顺序遍历数组 arr

  3. 对每个元素 \(x\)，执行状态转移： \[ f(x) \leftarrow f(x - d) + 1 \]

  4. 维护全局最大值作为答案

六、时间与空间复杂度分析

  • 时间复杂度： \[ O(n) \] 其中 \(n\) 为数组长度

  • 空间复杂度： \[ O(1) \] 值域大小固定（约 \(4\times10^4\)），与输入规模无关

七、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:
    // 数值映射后的最大范围：
    // 原值范围 [-20000, 20000]，整体平移 offset
    static const int maxn = 40005;
    static const int offset = 20000;

    int longestSubsequence(vector<int>& arr, int difference) {
        // f[v] 表示“以数值 (v - offset) 结尾的最长定差子序列长度”
        int f[maxn] = {};

        int mx = 1;   // 记录全局最大答案

        for (int x : arr) {
            // 将数值映射为数组下标
            int cur = x + offset;
            int prev = x - difference + offset;

            // 状态转移：
            // f(x) = f(x - difference) + 1
            int t = f[prev] + 1;

            // 更新当前数值对应的状态
            f[cur] = t;

            // 更新全局最大值
            if (t > mx) mx = t;
        }

        return mx;
    }
};