Length of Longest Fibonacci Subsequence LeetCode solution in Python

1
class Solution(
2
    object
3
):  # DP. Time Complexity: O(N^2), Space Complexity: O(NlogM), M = max(A)
4
    def lenLongestFibSubseq(self, A):
5
        index = {Ai: i for i, Ai in enumerate(A)}
6
        dp = collections.defaultdict(lambda: 2)
7
        ans = 0
8
        for k, Ak in enumerate(A):  # Following IJK idiom here
9
            for j in range(k - 1, 0, -1):
10
                i = index.get(Ak - A[j], None)
11
                if Ak - A[j] >= A[j]:
12
                    break  # Pruning for illegal Ai
13
                if i is not None and i < j:
14
                    cur_len = dp[j, k] = dp[i, j] + 1
15
                    ans = max(ans, cur_len)
16

17
        return ans  # ans is either 0 or >=3 for SURE