Skip to content

873. Length of Longest Fibonacci Subsequence 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int lenLongestFibSubseq(vector<int>& arr) {
    const int n = arr.size();
    int ans = 0;
    vector<vector<int>> dp(n, vector<int>(n, 2));
    unordered_map<int, int> numToIndex;

    for (int i = 0; i < n; ++i)
      numToIndex[arr[i]] = i;

    for (int j = 0; j < n; ++j)
      for (int k = j + 1; k < n; ++k) {
        const int ai = arr[k] - arr[j];
        if (ai < arr[j] && numToIndex.contains(ai)) {
          const int i = numToIndex[ai];
          dp[j][k] = dp[i][j] + 1;
          ans = max(ans, dp[j][k]);
        }
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int lenLongestFibSubseq(int[] arr) {
    final int n = arr.length;
    int ans = 0;
    int[][] dp = new int[n][n];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, 2));
    Map<Integer, Integer> numToIndex = new HashMap<>();

    for (int i = 0; i < n; ++i)
      numToIndex.put(arr[i], i);

    for (int j = 0; j < n; ++j)
      for (int k = j + 1; k < n; ++k) {
        final int ai = arr[k] - arr[j];
        if (ai < arr[j] && numToIndex.containsKey(ai)) {
          final int i = numToIndex.get(ai);
          dp[j][k] = dp[i][j] + 1;
          ans = Math.max(ans, dp[j][k]);
        }
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def lenLongestFibSubseq(self, arr: list[int]) -> int:
    n = len(arr)
    ans = 0
    numToIndex = {a: i for i, a in enumerate(arr)}
    dp = [[2] * n for _ in range(n)]

    for j in range(n):
      for k in range(j + 1, n):
        ai = arr[k] - arr[j]
        if ai < arr[j] and ai in numToIndex:
          i = numToIndex[ai]
          dp[j][k] = dp[i][j] + 1
          ans = max(ans, dp[j][k])

    return ans