873. Length of Longest Fibonacci Subsequence LeetCode Solution
In this guide, you will get 873. Length of Longest Fibonacci Subsequence LeetCode Solution with the best time and space complexity. The solution to Length of Longest Fibonacci Subsequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Length of Longest Fibonacci Subsequence
A sequence x1, x2, …, xn is Fibonacci-like if:
n >= 3
xi + xi+1 == xi+2 for all i + 2 <= n
Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0.
A subsequence is derived from another sequence arr by deleting any number of elements (including none) from arr, 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:
Input: arr = [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:
Input: arr = [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].
873. Length of Longest Fibonacci Subsequence LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
873. Length of Longest Fibonacci Subsequence LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
873. Length of Longest Fibonacci Subsequence LeetCode Solution in Python
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 # code by PROGIEZ
