leetcode 873

问题

A sequence X_1, X_2, ..., X_n is fibonacci-like if:

  • n >= 3
  • X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.

(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)

Example 1:

1
2
3
4
Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

1
2
3
4
5
Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].

Note:

  • 3 <= A.length <= 1000
  • 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
  • (The time limit has been reduced by 50% for submissions in Java, C, and C++.)

分析

思路1: 每两个数字就可以确定一条 Fibonacci 数列，我们可以先确定，每一个Fibonacci 数列的首两个数字，然后依次判断，这个数列中的数字是否在数组A中，查找每个数字是否可在可以使用hash表。时间复杂度$O(n^2 logM)$， 其中 $ M = max(A[i])$，假设 Fibonacci 数列中最大的数可能是M，则由于其数列的增长是指数形式的，所以最多查找 $logM$ 次。

思路2: 使用DP算法，$dp[a][b]$ 表示以 $a, b$ 结尾的 Fibonacci 数列的最大长度。则有 $dp[a][b] = dp[b-a][a] + 1$， 若 $dp[b-a][a]$ 不存在则为 2。在本题中我们可以使用下标来代替具体的数值。则有 $ dp[i][j] $ 表示以 $A[i], A[j]$ 结尾的 Fibonacci 数组的最大长度，则 $dp[i][j] = dp[k][i] + 1$，其中 $ A[k] = A[j] - A[i] $ ，且有 $ k < i$，因此，我们可以使用一个 $ unordered_map mp $ 来保存 $val$ 到 $index$ 之间的映射。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int ans = 0;
        unordered_set<int> st(A.begin(), A.end());
        int n = A.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                int a = A[i], b = A[j], l = 2;
                while (st.find(a+b) != st.end()) {
                    b = a+b, a = b-a, l++;  // 注意更新的顺序及关系
                }
                ans = max(ans, l);
            }
        }
        return ans > 2? ans: 0;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> dp(n, vector<int>(n, 2));
        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 k = (mp.find(A[j]-A[i])!=mp.end()? mp[A[j]-A[i]]: -1);
                if (k != -1 && k < i) {
                    dp[i][j] = dp[k][i] + 1;
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans>2? ans: 0;
    }
};