最长等差子序列 (Longest Arithmetic Subsequence)

题目描述 给定一个长度为 $n$ 的整数序列 $A$。你需要从该序列中选出一个子序列（不要求连续），使得该子序列构成一个等差数列。你的任务是求出这个等差子序列的最大长度。

等差数列是指从第二项起，每一项与它的前一项之差等于同一个常数（称为公差）的数列。

输入格式 第一行包含一个整数 $n$，表示序列的长度。 第二行包含 $n$ 个整数，表示序列 $A_0, A_1, \dots, A_{n-1}$。

输出格式 输出一个整数，表示最长等差子序列的长度。

样例输入

5
9 4 7 2 10

样例输出

3

数据范围与提示

• 对于 $50\%$ 的数据，$n \le 500$，$A_i$ 的取值范围较小。
• 对于 $100\%$ 的数据，$n \le 2000$，$0 \le A_i \le 10^9$。
• 注意：公差可能为负数，且任意两个数均可视为长度为 2 的等差数列。

OI 教练课：从“升维”到“稀疏建模”

1. 为什么一维 DP 不够用了？

在解决最长递增子序列（LIS）时，我们定义 dp[i] 表示以第 $i$ 个数结尾的最优解。这是因为 LIS 只需要知道“上一个数是谁”。 但等差数列具有三元关系约束。要确定 $A_k, A_j, A_i$ 是否成等差，必须满足 $A_i - A_j = A_j - A_k$。如果我们只知道以 $A_j$ 结尾的最长长度，我们无法得知它的公差是什么，也就无法判断 $A_i$ 能否接在后面。

2. 状态的维度升级

为了记录“历史公差”，我们需要增加一维：

• 状态定义：dp[i][diff] 表示以索引 $i$ 结尾，且公差为 diff 的等差子序列的最长长度。
• 状态转移：遍历 $i$ 之前的所有 $j$ ($j < i$)：
  1. 计算当前公差 d = A[i] - A[j]。
  2. 如果 dp[j][d] 已经存在，则 dp[i][d] = dp[j][d] + 1。
  3. 如果不存在，说明 $(A_j, A_i)$ 是新数列的开头，dp[i][d] = 2。

3. 稀疏状态管理（Hash Map 优化）

当 $A_i$ 范围达到 $10^9$ 时，公差 diff 的范围也会非常大，直接开二维数组 dp[2000][2*10^9] 会导致内存爆炸。

• 观察：对于每个固定的 $i$，有效的 diff 最多只有 $i$ 个。
• 对策：使用哈希表向量 std::vector<std::unordered_map<int, int>> dp。这样只为实际存在的 (i, diff) 对分配空间。

4. 类斐波那契序列的拓展

如果题目变为“类斐波那契子序列”（$A_k + A_j = A_i$），逻辑依然相同：

• 通过 $A_i - A_j$ 锁定我们需要寻找的“前项”数值 $A_k$。
• 利用预处理的数值到索引的映射（val_to_index）实现 $O(1)$ 查找，从而将 $O(N^3)$ 的暴力枚举优化至 $O(N^2)$。

算法逻辑流程图 (Mermaid)

graph TD
    Start("开始分析") --> Init("初始化 maxLength = 0")
    Init --> CreateDP("创建 dp 数组: 元素为哈希表 unordered_map")
    CreateDP --> OuterLoop("外层循环 i 从 0 到 n-1")
    OuterLoop --> InnerLoop("内层循环 j 从 0 到 i-1")
    InnerLoop --> CalcDiff("计算公差 d = A_i - A_j")
    
    CalcDiff --> CheckExist{"dp_j 中是否存在公差 d ?"}
    CheckExist -- "是" --> Extend("length = dp_j_d + 1")
    CheckExist -- "否" --> NewSeq("length = 2")
    
    Extend --> UpdateDP("更新 dp_i_d = length")
    NewSeq --> UpdateDP
    
    UpdateDP --> MaxUpdate("maxLength = max(maxLength, length)")
    MaxUpdate --> InnerNext("继续内层循环 j")
    InnerNext --> InnerLoop
    
    InnerLoop -- "j 遍历结束" --> OuterNext("继续外层循环 i")
    OuterNext --> OuterLoop
    
    OuterLoop -- "i 遍历结束" --> End("返回 maxLength")

关键避坑指南（Must Remember）

1. 差一错误 (Off-by-One)：
   • 记住由 A[j] 和 A[i] 组成的最小等差数列长度是 2。在更新 dp[i][d] 时，如果找不到前驱，默认值应设为 2。
2. 全局最优解更新：
   • 答案不一定出现在序列的末尾，必须在内层循环每次计算出新的 length 时，立刻更新全局最大值变量。
3. 时间与空间权衡：
   • unordered_map 虽然平均复杂度是 $O(1)$，但在极少数数据下可能发生哈希冲突退化到 $O(N)$。在 NOI 竞赛中，如果 $A_i$ 范围较小，使用离散化或偏移量数组（Offset Array）通常比哈希表更稳健。
4. 重复项处理：
   • 如果序列中有重复数字（如 4, 4, 4），公差为 0。本模板通过覆盖更新 dp[i][0]，可以自然地处理这种情况，无需额外逻辑。