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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LenLongestFibSubseq(int[] arr) {
int n = arr.Length;
var index = new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
index[arr[i]] = i;
}
var dp = new Dictionary<(int, int), int>();
int maxLen = 0;
for (int k = 0; k < n; k++) {
for (int j = 0; j < k; j++) {
if (index.TryGetValue(arr[k] - arr[j], out int i) && i < j) {
var cand = dp.TryGetValue((i, j), out int val) ? val : 2;
cand++;
dp[(j, k)] = cand;
maxLen = Math.Max(maxLen, cand);
}
}
}
return maxLen >= 3 ? maxLen : 0;
}
}The C# solution mirrors the dynamic programming approach in Java. A dictionary maps values to indices for quick checks. If arr[k] - arr[j] is a valid earlier sequence number, the program calculates and updates the length of subsequences appropriately, making full use of C#'s tuple management and dictionary operations.