Leetcode 0873 Length of Longest Fibonacci Subsequence

Problem statement

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/

Solution

Let dp(i, j) be the longest subsequence such that last two elements are i and j. Then we check j - i and if it is in set of our numbers and it is smaller than i, we return dp(j - i, i) + 1. In the opposite case we return 2. In the end we go through all pairs and find maximum.

Complexity

Time complexity is O(n^2), space complexity as well.

Code

class Solution:
    def lenLongestFibSubseq(self, arr):
        set_arr = set(arr)
        
        @lru_cache(None)
        def dp(i, j):
            if j >= 2*i or j - i not in set_arr: return 2
            else: return dp(j - i, i) + 1
            
        ans = max(dp(i, j) for i, j in combinations(arr, 2))
        return ans if ans > 2 else 0