Algorithm
Problem Name: 873. Length of Longest Fibonacci Subsequence
A sequence x1, x2, ..., xn is Fibonacci-like if:
n >= 3xi + xi+1 == xi+2for alli + 2 <= n
Given 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] <= 109
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
start coding...Input
arr = [1,2,3,4,5,6,7,8]
Output
5
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def lenLongestFibSubseq(self, A):
n, pair, res, back = len(A), {}, 0, set()
for i in range(n):
back.add(A[i])
j = i + 1
mx = 2 * A[i]
while j < n and A[j] < mx:
if (A[j] - A[i], A[i]) in pair:
pair[(A[i], A[j])] = pair[(A[j] - A[i], A[i])] + 1
else:
pair[(A[i], A[j])] = A[j] - A[i] in back and 3 or 2
res = max(res, pair[(A[i], A[j])])
j += 1
return res > 2 and res or 0
Input
arr = [1,2,3,4,5,6,7,8]
Output
5