LeetCode剑指 Offer II 093 最长斐波那契数列

LeetCode剑指 Offer II 093 最长斐波那契数列

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:

        n, loc, ans = len(arr), {}, 0
        for i in range(n): loc[arr[i]] = i
        f = [[0] * n for i in range(n)]

        for i in range(n):
            for j in range(i - 1, -1, -1):
                if arr[j] * 2 <= arr[i]: break
                else:
                    arr_k = arr[i] - arr[j]
                    if arr_k in loc:
                        k = loc[arr_k]
                        f[i][j] = max(f[j][k] + 1, 3)
                        ans = max(ans, f[i][j])
        
        return ans