Longest Arithmetic Subsequence

In this problem, you are given an array of integers nums, and the goal is to find the length of the longest arithmetic subsequence.

An arithmetic subsequence is a subsequence where the difference between consecutive elements is constant. A subsequence is an array derived from another array by deleting some or no elements without changing the order of the remaining elements.

Solution

We can use dynamic programming to solve this problem. Specifically, we can use a hash table to store the maximum length of an arithmetic subsequence ending at a particular index with a given common difference.

Here is the code implementation in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i][diff] will store the length of the arithmetic subsequence ending at index i with common difference diff
        dp = [defaultdict(int) for _ in range(n)]
        max_length = 0
        
        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                # If there is a previous arithmetic subsequence with the same difference, we extend it
                # Otherwise, we start a new arithmetic subsequence with length 2
                dp[i][diff] = dp[j][diff] + 1
                max_length = max(max_length, dp[i][diff] + 1)
        
        return max_length

Explanation

• We initialize a list dp of dictionaries, where dp[i][diff] represents the length of the arithmetic subsequence ending at index i with a common difference diff.
• We iterate through all pairs of elements in the array, and for each pair, we calculate the difference diff and update dp[i][diff].
• If there is a previous arithmetic subsequence with the same difference, we extend its length by 1; otherwise, we start a new arithmetic subsequence with length 2 (i.e., the pair itself).
• We keep track of the maximum length throughout this process and return it as the final result.

This code runs in O(n^2) time complexity and O(n * d) space complexity, where n is the length of the nums array, and d is the number of unique differences between elements in the array.