Leetcode 1027. Longest Arithmetic Subsequence

Problem statement

https://leetcode.com/problems/longest-arithmetic-subsequence/

Solution

Let best[i, d] means the longest arithmetic subsequence, which ends with element A[i] and have difference d.

Complexity

It is O(n^2) for time and space.

Code

class Solution:
    def longestArithSeqLength(self, A):
        best = Counter()
        for i in range(len(A)):
            for j in range(i):
                d = A[i] - A[j]
                best[(i,d)] = max(best[(i,d)], 1+best[(j,d)])
        return max(best.values()) + 1