MediumNo. 0873
Length of Longest Fibonacci Subsequence — LeetCode 873 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Hash Table, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- 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].
Python solution
class Solution:
def lenLongestFibSubseq(self, arr: List[int]) -> int:
n = len(arr)
f = [[0] * n for _ in range(n)]
d = {x: i for i, x in enumerate(arr)}
for i in range(n):
for j in range(i):
f[i][j] = 2
ans = 0
for i in range(2, n):
for j in range(1, i):
t = arr[i] - arr[j]
if t in d and (k := d[t]) < j:
f[i][j] = max(f[i][j], f[j][k] + 1)
ans = max(ans, f[i][j])
return ansComplexity
- Time
- O(n2)
- Space · auxiliary
- O(n2)where n is the length of the array arr
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 873. Length of Longest Fibonacci Subsequence is filed here because LeetCode tags it Dynamic Programming, which is the vocabulary this hub collects.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0139 | Word Break | Medium |
| 0140 | Word Break II | Hard |
| 0691 | Stickers to Spell Word | Hard |
| 0740 | Delete and Earn | Medium |
| 0792 | Number of Matching Subsequences | Medium |
| 0823 | Binary Trees With Factors | Medium |
Frequently asked questions
- How hard is LeetCode 873. Length of Longest Fibonacci Subsequence?
LeetCode 873. Length of Longest Fibonacci Subsequence is rated Medium on LeetCode.
- What is the time complexity of LeetCode 873. Length of Longest Fibonacci Subsequence?
The Python solution on this page runs in O(n2).
- What is the space complexity of LeetCode 873. Length of Longest Fibonacci Subsequence?
The Python solution on this page uses O(n2), where n is the length of the array \textit{arr} auxiliary space.
- What topics does LeetCode 873. Length of Longest Fibonacci Subsequence cover?
LeetCode 873. Length of Longest Fibonacci Subsequence is tagged Array, Hash Table and Dynamic Programming on LeetCode.