https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/
https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/discuss/152332/Java-clean-DP-O(n2)-time-O(n2)-space
Approach 1: Brute Force with Set
A sequence
X_1, X_2, ..., X_n is fibonacci-like if:n >= 3X_i + X_{i+1} = X_{i+2}for alli + 2 <= n
Given a strictly increasing array
A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.
(Recall that a subsequence is derived from another sequence
A by deleting any number of elements (including none) from A, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)
X. https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/discuss/152343/C%2B%2BJavaPython-Check-Pair
https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/discuss/152332/Java-clean-DP-O(n2)-time-O(n2)-space
Then we have
The complexity reduce to
In C++/Java, I use 2D dp and index as key.
In Python, I use value as key.
https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/discuss/152332/Java-clean-DP-O(n2)-time-O(n2)-space
dp[a, b] represents the length of fibo sequence ends up with (a, b)Then we have
dp[a, b] = (dp[b - a, a] + 1 ) or 2The complexity reduce to
O(N^2).In C++/Java, I use 2D dp and index as key.
In Python, I use value as key.
public int lenLongestFibSubseq(int[] A) {
int res = 0;
int[][] dp = new int[A.length][A.length];
Map<Integer, Integer> index = new HashMap<>();
for (int j = 0; j < A.length; j++) {
index.put(A[j], j);
for (int i = 0; i < j; i++) {
int k = index.getOrDefault(A[j] - A[i], -1);
dp[i][j] = (A[j] - A[i] < A[i] && k >= 0) ? dp[k][i] + 1 : 2;
res = Math.max(res, dp[i][j]);
}
}
return res > 2 ? res : 0;
}
Approach 2: Dynamic Programming
- Time Complexity: , where is the length of
A. - Space Complexity: , where is the largest element of
A. We can show that the number of elements in a subsequence is bounded by where is the minimum element in the subsequence.
Think of two consecutive terms
A[i], A[j] in a fibonacci-like subsequence as a single node (i, j), and the entire subsequence is a path between these consecutive nodes. For example, with the fibonacci-like subsequence (A[1] = 2, A[2] = 3, A[4] = 5, A[7] = 8, A[10] = 13), we have the path between nodes (1, 2) <-> (2, 4) <-> (4, 7) <-> (7, 10).
The motivation for this is that two nodes
(i, j) and (j, k) are connected if and only if A[i] + A[j] == A[k], and we needed this amount of information to know about this connection. Now we have a problem similar to Longest Increasing Subsequence.
Algorithm
Let
longest[i, j] be the longest path ending in [i, j]. Then longest[j, k] = longest[i, j] + 1 if (i, j) and (j, k) are connected. Since i is uniquely determined as A.index(A[k] - A[j]), this is efficient: we check for each j < k what i is potentially, and update longest[j, k] accordingly.- Time Complexity: , where is the length of
A. - Space Complexity: , where is the largest element of
A. We can show that the number of elements in a subsequence is bounded by where is the minimum element in the subsequence.
public int lenLongestFibSubseq(int[] A) {
int N = A.length;
Map<Integer, Integer> index = new HashMap();
for (int i = 0; i < N; ++i)
index.put(A[i], i);
Map<Integer, Integer> longest = new HashMap();
int ans = 0;
for (int k = 0; k < N; ++k)
for (int j = 0; j < k; ++j) {
int i = index.getOrDefault(A[k] - A[j], -1);
if (i >= 0 && i < j) {
// Encoding tuple (i, j) as integer (i * N + j)
int cand = longest.getOrDefault(i * N + j, 2) + 1;
longest.put(j * N + k, cand);
ans = Math.max(ans, cand);
}
}
return ans >= 3 ? ans : 0;
}
public int lenLongestFibSubseq(int[] A) {
int n = A.length;
int[][] dp = new int[n][n];
Map<Integer, Integer> pos = new HashMap<>();
for (int i = 0; i < n; i++) {
pos.put(A[i], i);
for (int j = i; j < n; j++) {
dp[i][j] = 2;
}
}
for (int j = 2; j < n; j++) {
for (int i = j - 1; i > 0; i--) {
int prev = A[j] - A[i];
if (prev >= A[i]) {
break;
}
if (!pos.containsKey(prev)) {
continue;
}
dp[i][j] = dp[pos.get(prev)][i] + 1;
}
}
int result = 0;
for (int j = 2; j < n; j++) {
for (int i = 1; i < n - 1; i++) {
if (dp[i][j] > 2) {
result = Math.max(result, dp[i][j]);
}
}
}
return result;
}
For each A[i] find previous 2 elements sum up to A[i],
then it's a classical follow up problem for Two Sum
if 2 elements A[l] and A[r] sum up to A[i]
return the max(all posible dp[r][i])
then it's a classical follow up problem for Two Sum
167. Two Sum II - Input array is sortedif 2 elements A[l] and A[r] sum up to A[i]
dp[r][i]: length of longest fibonacchi sequence end with A[r], A[i]dp[r][i] = dp[l][r] + 1return the max(all posible dp[r][i])
public int lenLongestFibSubseq(int[] A) {
int n = A.length;
int max = 0;
int[][] dp = new int[n][n];
for (int i = 1; i < n; i++) {
int l = 0, r = i - 1;
while (l < r) {
int sum = A[l] + A[r];
if (sum > A[i]) {
r--;
} else if (sum < A[i]) {
l++;
} else {
dp[r][i] = dp[l][r] + 1;
max = Math.max(max, dp[r][i]);
r--;
l++;
}
}
}
return max == 0 ? 0 : max + 2;
}
Time Complexity:
Space Complexity:
O(N^2)Space Complexity:
O(N^2
- it doesn't work, it returns 3 for {3,2,1}
Every Fibonacci-like subsequence has each two adjacent terms determine the next expected term. For example, with
2, 5, we expect that the sequence must continue 7, 12, 19, 31, etc.
We can use a
Set structure to determine quickly whether the next term is in the array A or not. Because of the exponential growth of these terms, there are at most 43 terms in any Fibonacci-like subsequence that has maximum value .
Algorithm
For each starting pair
A[i], A[j], we maintain the next expected value y = A[i] + A[j] and the previously seen largest value x = A[j]. If y is in the array, then we can then update these values (x, y) -> (y, x+y).
Also, because subsequences are only fibonacci-like if they have length 3 or more, we must perform the check
ans >= 3 ? ans : 0 at the end.- Time Complexity: , where is the length of
A, and is the maximum value ofA. - Space Complexity: , the space used by the set
S.
public int lenLongestFibSubseq(int[] A) {
int N = A.length;
Set<Integer> S = new HashSet();
for (int x : A)
S.add(x);
int ans = 0;
for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j) {
/*
* With the starting pair (A[i], A[j]), y represents the future expected value
* in the fibonacci subsequence, and x represents the most current value found.
*/
int x = A[j], y = A[i] + A[j];
int length = 2;
while (S.contains(y)) {
// x, y -> y, x+y
int tmp = y;
y += x;
x = tmp;
ans = Math.max(ans, ++length);
}
}
return ans >= 3 ? ans : 0;
}
