bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
Medium1-D Dynamic ProgrammingLC 873

Length of Longest Fibonacci Subsequence

A sequence x1, x2, ..., xn is Fibonacci-like if: n >= 3 xi + xi+1 == xi+2 for all i + 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].

Asked at 2 companies
AmazonBaidu
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode