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.
1def lenLongestFibSubseq(arr):
2 s = set(arr)
3 max_len = 0
4 n = len(arr)
5
6 for i in range(n-1):
7 for j in range(i+1, n):
8 x, y = arr[i], arr[j]
9 length = 2
10 while x + y in s:
11 x, y = y, x + y
12 length += 1
13 max_len = max(max_len, length)
14
15 return max_len if max_len >= 3 else 0The function initializes a set s containing all elements of the array for constant-time lookups. It iterates through each pair of elements (arr[i], arr[j]) using two loops, treating them as the first two elements of a potential Fibonacci subsequence. While the sum of the last two elements exists in the set, it increases the subsequence length. If a valid Fibonacci-like sequence of length at least 3 is found, it updates max_len.
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.