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.
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.