Longest Arithmetic Subsequence

Find the length of the longest subsequence with a constant difference.

dp subsequence hashmap

You are given a non-empty list of integers `nums`. An **arithmetic subsequence** is a subsequence of `nums` (elements appear in order, but not necessarily contiguous) where the difference between consecutive elements is constant. A subsequence of length 1 or 2 is always arithmetic (any difference). Write a function `longest_arithmetic_subsequence(nums)` that returns the length of the longest arithmetic subsequence.

For example, in `[3, 6, 9, 12]` the longest arithmetic subsequence has length 4 (difference 3). In `[1, 7, 10, 13, 14, 19]`, the longest is `[7, 10, 13]` or `[1, 7, 13, 19]`? Actually `[1, 7, 13, 19]` has differences 6, 6, 6 — length 4. Return the maximum length.

Implement the function exactly as specified. The input list may contain negative numbers and duplicates. The order of the original list must be preserved in the subsequence.

Constraints

1 <= len(nums) <= 1000
-10^9 <= nums[i] <= 10^9
The function must run in O(n^2) time and O(n^2) space or better.

Example

>>> longest_arithmetic_subsequence([3, 6, 9, 12])
4
>>> longest_arithmetic_subsequence([1, 7, 10, 13, 14, 19])
4
>>> longest_arithmetic_subsequence([5])
1
>>> longest_arithmetic_subsequence([1, 2, 3, 4])
4

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about extending subsequences by their last element and the common difference.

For each pair of indices (i, j) with i < j, what is the difference? Can you extend a subsequence ending at i with that difference?

Use a dictionary keyed by (index, diff) to store the longest subsequence ending at that index with that difference.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.