Longest Arithmetic Subsequence [Python]

Problem.

Naive approach - Exponential time

One of the ways we could solve this is to get all the sub-sequences and see if they are arithmetic. Pretty straight forward.

Now how do we generate all the subsequences? One of the ways could be like this:

def generate_subseq(seq):
    sequences = [[]]
    for num in seq:
        new_sequences = []
        for sub in sequences:
            copy = sub[:]
            copy.append(num)
            new_sequences.append(copy)
        sequences.extend(new_sequences)
    
    return sequences

seq = [1, 2, 3, 4]
print(generate_subseq(seq))

The time complexity of the above is O(2^n) since for every entry we can either select it or not select it.

And for every sub sequence we can check if its Arithmetic in O(n)

Can we do better?

Like in most cases if someone asks you this, chances are there is a better/faster way to solve the problem. Better time complexities are preferred over better space complexities.

Dynamic Programming - O(n^2)

The idea here is that from any index i, we find the difference between elements at index i and all the indexes before i, which gives us j -> 0 to i-1 [0, i).

Now that we have a difference diff, we also need to know if there is a subsequence that ends at index j with the difference diff. We need some way to store the information of all the subsequences that ends at j, to figure out if we are continuing a subsequence or starting a new one.

For example a new subsequence would be [5, 7], when we are at 7 we have a new subsequence that maintains the difference of 2 that ends at 7 or index 1.

A continuing subsequence would be [1, 3, 5, 7], where if we were at 7 and look at 5, we want to know that at 5 there is a subsequence of length 3 which maintains a difference of 2, so that we can add 7 to the previous subsequence and store the info.

Another thing to keep in mind would be that there could be multiple sequence with different differences that could end at a particular position in our original sequence or there could be shorter sequences with the same difference that ends at the same index, we keep the one with the maximum count.

Looking at the code below should give you greater clarity.

def longest_arithmetic_subsequence(A):
    n = len(A)
    if n < 3:
        return n
    
    counts = [{} for _ in A]
    max_count = 0
    
    for i in range(0, len(A)):
        for j in range(0, i):
            diff = A[i] - A[j]
            counts[i][diff] = max(counts[i].get(diff, 1), counts[j].get(diff, 1) + 1)
            max_count = max(max_count, counts[i][diff])
    
    return max_count

Use get() method of the dictionary to reduce lines of code. It reduces the volume by a lot.