Sponsored
Sponsored
This approach leverages a two-pointer mechanism combined with a HashSet to efficiently find Fibonacci-like sequences. Given the strictly increasing nature of the array, we can use a set for quick lookup to determine if the sum of two numbers exists in the array, thus confirming a Fibonacci-like sequence.
Time Complexity: O(n^2 * logM), where n is the length of the array and M is the maximum value in the array (for set operations).
Space Complexity: O(n) due to the HashSet used for lookups.
1function lenLongestFibSubseq(arr) {
2 const s = new Set(arr);
3 let maxLen = 0;
4 const n = arr.length;
5
6 for (let i = 0; i < n - 1; i++) {
7 for (let j = i + 1; j < n; j++) {
8 let x = arr[i], y = arr[j];
9 let length = 2;
10 while (s.has(x + y)) {
11 const temp = x + y;
12 x = y;
13 y = temp;
14 length++;
15 }
16 maxLen = Math.max(maxLen, length);
17 }
18 }
19
20 return maxLen >= 3 ? maxLen : 0;
21}This solution uses an array-backed set for fast lookups. By iterating over every possible starting pair (arr[i], arr[j]), the code verifies if a subsequent valid Fibonacci sequence can be formed. Upon successful extension of the sequence, the code updates the maximum length found.
In this approach, dynamic programming is used to maintain a table where dp[i][j] denotes the length of the Fibonacci-like subsequence ending with arr[i] and arr[j]. Whenever a valid predecessor pair (arr[k], arr[i]) is found such that arr[k] + arr[i] = arr[j], the table is updated, calculating a maximal subsequence length.
Time Complexity: O(n^2), where n is the length of the array, since every pair is compared.
Space Complexity: O(n^2), as a map stores the length for each pair.
1import java.util.HashMap;
2
This Java solution is based on dynamic programming with a HashMap to efficiently explore and track subsequences. It first constructs a map to identify indices by value in constant time. For each pair (j, k), if a valid predecessor exists, the dp table is updated, storing the sequence length.