A sequence x1, x2, ..., xn is Fibonacci-like if:
n >= 3xi + xi+1 == xi+2 for all i + 2 <= nGiven a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0.
A subsequence is derived from another sequence arr by deleting any number of elements (including none) from arr, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].
Example 1:
Input: arr = [1,2,3,4,5,6,7,8] Output: 5 Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].
Example 2:
Input: arr = [1,3,7,11,12,14,18] Output: 3 Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].
Constraints:
3 <= arr.length <= 10001 <= arr[i] < arr[i + 1] <= 109class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length, maxStreak = 0;
Set<Integer> set = Arrays.stream(arr).boxed().collect(Collectors.toSet());
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int fib1 = arr[i], fib2 = arr[j], fib3 = fib1 + fib2, streak = 2;
while (set.contains(fib3)) {
streak++;
fib1 = fib2;
fib2 = fib3;
fib3 = fib1 + fib2;
}
maxStreak = Math.max(streak, maxStreak);
}
}
return maxStreak > 2 ? maxStreak : 0;
}
}class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length, maxStreak = 0;
int[][] dp = new int[n][n];
for (int curr = 2; curr < n; curr++) {
int lt = 0, rt = curr - 1;
while (lt < rt) {
int sum = arr[lt] + arr[rt];
if (sum > arr[curr])
rt--;
else if (sum < arr[curr])
lt++;
else {
dp[rt][curr] = dp[lt][rt] + 1; // streak inc.
maxStreak = Math.max(maxStreak, dp[rt][curr]);
rt--;
lt++;
}
}
}
return maxStreak == 0 ? 0 : maxStreak + 2;
}
}