873. Length of Longest Fibonacci Subsequence
Medium
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] <= 10^9
func lenLongestFibSubseq(arr []int) int {
m := make(map[int]bool)
ans := 0
for _, n := range arr {
m[n] = true
}
for i:=0; i<len(arr); i++ {
for j:=i + 1; j<len(arr); j++ {
first, second, third := arr[i], arr[j], arr[i] + arr[j]
length := 2
for m[third] {
first = second
second = third
third = first + second
length++
}
ans = max(ans, length)
}
}
if ans < 3 { return 0 }
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Last modified 5mo ago