Problem statement

https://https://binarysearch.com/problems/Longest-Arithmetic-Subsequence/

Solution

Equal to Leetcode 1027. Longest Arithmetic Subsequence. 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 solve(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])
        if not A: return 0
        if not best: return 1
        return max(best.values()) + 1