最长类斐波那契子序列 (Longest Fibonacci-Like Subsequence)

如果序列 $X_1, X_2, \dots, X_n$ 满足下列条件，则说它是类斐波那契的：

1. $n \ge 3$
2. 对于所有 $i \ge 3$，都有 $X_{i-2} + X_{i-1} = X_i$

给定一个严格递增的正整数数组 nums，返回 nums 中最长类斐波那契子序列的长度。如果不存在这样的子序列，返回 0。

OI 教练课：从“等差”到“等和”的升维打击

孩子，如果你已经掌握了“最长等差子序列”，那么这道题对你来说只是关系式的变体。我们依然要处理三元依赖关系。

核心知识点清单（Tutorial Chapters）

1. 状态的必然升维 (Beyond 1D DP)

   • 类斐波那契序列的下一项由前两项共同决定。仅用 dp[i] 无法表达序列的“惯性”。
   • 知识点： 必须定义二维状态 dp[j][i]，表示以索引 $j$ 和 $i$ 结尾的子序列长度（其中 $j < i$）。

2. 目标值的逆向搜索 (Finding Preceding Term)

   • 若当前两项为 $A[j], A[i]$，则其前驱项必须是 $pre = A[i] - A[j]$。
   • 知识点： 将“寻找满足条件的 $k$”转化为“在数组中查找特定值 $pre$”。

3. 空间换时间的极致：哈希表优化 (Hash Map Optimization)

   • 在 $O(n^2)$ 的枚举中，如果再暴力扫描 $pre$ 的位置，复杂度会退化到 $O(n^3)$。
   • 知识点： 预处理一个 unordered_map<int, int> val_to_idx，实现从“数值”到“下标”的 $O(1)$ 映射。

4. 严格递增约束 (Strict Constraints)

   • 知识点： 查找到的 $k$ 必须满足 $k < j$，才能保证索引的合法递增。同时由于原数组严格递增，$A[k] < A[j]$ 自动隐含了 $pre < A[j]$，即 $A[i] - A[j] < A[j]$（等价于 $A[i] < 2 \cdot A[j]$）。

算法逻辑流程图 (Mermaid 伪代码提示)

graph TD
    A("开始分析") --> B("预处理: 将所有 nums(i) 及其索引 i 存入哈希表")
    B --> C("初始化 dp(j,i) 全为 2")
    C --> D("外层循环 i 从 0 到 n-1")
    D --> E("内层循环 j 从 0 到 i-1")
    E --> F("计算目标前驱值 target = nums(i) - nums(j)")
    
    F --> G{"target 是否在哈希表中 且 其索引 k 小于 j ?"}
    
    G -- "是" --> H("执行转移: dp(j,i) = dp(k,j) + 1")
    G -- "否" --> I("保持当前长度为 2")
    
    H --> J("更新全局最大长度 ans = max(ans, dp(j,i))")
    I --> J
    
    J --> K("结束内层循环 j")
    K --> L("结束外层循环 i")
    L --> M("返回 ans 大于 2 ? ans : 0")

样例数据 (Sample Data)

样例输入

8
1 2 3 4 5 6 7 8

样例输出

5

样例解释 最长的类斐波那契子序列为 [1, 2, 3, 5, 8]。

数据范围与说明 (Constraints)

• 对于 $30\%$ 的数据：$n \le 100$
• 对于 $60\%$ 的数据：$n \le 500$
• 对于 $100\%$ 的数据：$3 \le n \le 2500$，$1 \le nums[i] \le 10^9$
• 数组 nums 是严格递增的（这意味着我们不需要担心重复元素干扰下标查找）。

对应例题洛谷链接

此类问题的核心在于“二维状态表示”与“哈希/二分优化查找”。

1. 本题对应（最长类斐波那契）： P8623 [蓝桥杯 2015 国 ABC] 齐头并进 (注：此类三元关系搜索在蓝桥杯/NOI普及组中高频出现)

2. 进阶练习（三元等差关系）： P4933 大师 (这是资料中提到的 LAS 问题的直接对应，掌握了斐波那契，等差序列也就迎刃而解)

教练寄语： 斐波那契和等差数列的 DP 模板是一对双生子。区别仅在于：等差找的是 $A[i]-d$，而斐波那契找的是 $A[i]-A[j]$。掌握了下标映射和状态升维，你就掌握了子序列问题的进阶钥匙。