题目描述

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0。

（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如，[3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

样例

输入：[1,2,3,4,5,6,7,8]
输出：5
解释：
最长的斐波那契式子序列为：[1,2,3,5,8]。

输入：[1,3,7,11,12,14,18]
输出：3
解释：
最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18]。

限制

• 3 <= A.length <= 1000
• 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
  *（对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）

算法1

(暴力枚举) $O(n^2 \log M)$

1. 枚举斐波那契数列的前两个数字，然后用集合暴力判定数列能延续的长度。
2. 因为斐波那契数列上升是指数级的，所以答案最多不超过 $O(\log M)$，其中 $M$ 是最大的数字。
3. 我们可以加上一个剪枝，如果第一个数字的 ans + 2 倍超过了数组中最大的数字，则此次判定必定不会超过当前答案。

时间复杂度

• 枚举开头两个数字的时间复杂度为 $O(n^2)$。
• 暴力判定的时间复杂度为 $O(\log M)$。
• 故总时间复杂度为 $O(n^2 \log M)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储集合。

C++ 代码

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        unordered_set<int> nums(A.begin(), A.end());
        int n = A.size();

        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int x = A[i], y = A[j];

                if ((long long)(x) * (ans + 2) > A.back())
                    continue;

                int cnt = 0;
                while (nums.find(x + y) != nums.end()) {
                    cnt++;
                    int t = x + y;
                    x = y; y = t;
                }

                ans = max(ans, cnt);
            }

        return ans == 0 ? 0 : ans + 2;
    }
};

算法2

(动态规划) $O(n^2)$

1. 设状态 $f(i, j)$ 表示以 nums[i] 和 nums[j] 结尾的斐波那契数列的最大长度，其中 $i < j$。
2. 初始化全部为 0。
3. 转移时，如果存在一个下标 $k$，满足 $k < i$ 且 $nums[k] = nums[j] - nums[i]$，则转移 $f(i, j) = f(k, i) + 1$，这一步可以用哈希表判定。
4. 最终答案为 $f$ 数组中的最大值。

时间复杂度

• 状态数为 $O(n^2)$，每次转移仅需要常数时间，故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要 $O(n^2)$ 的额外空间存储哈希表和动态规划的状态。

C++ 代码

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> f(n, vector<int>(n, 0));

        unordered_map<int, int> mp;
        for (int i = 0; i < n; i++)
            mp[A[i]] = i;

        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int d = A[j] - A[i];
                if (mp.find(d) != mp.end() && mp[d] < i) {
                    f[i][j] = f[mp[d]][i] + 1;
                    ans = max(ans, f[i][j]);
                }
            }

        return ans == 0 ? 0 : ans + 2;
    }
};