1027. Longest Arithmetic Subsequence

Problem¶

Return the maximum length of a subsequence whose consecutive elements have the same difference.

nums = [20, 1, 15, 3, 10, 5, 8] -> 4
subsequence = [20, 15, 10, 5], difference = -5

Key trick¶

Use dynamic programming where dp[i][d] is the longest arithmetic subsequence ending at index i with difference d; extend it from every earlier index j.

Trap¶

A value alone is not a unique endpoint because duplicates can occur at different indices.
Differences may be zero or negative.
Multiple subsequences can end at the same index with different differences.
A pair starts a valid arithmetic subsequence of length 2.

Why is it interesting?¶

It turns a subsequence problem into pairwise transitions by adding the common difference to the DP state.

Python solution¶

class Solution:
    def longestArithSeqLength(self, nums: list[int]) -> int:
        n = len(nums)
        # dp[i][d] is the best length ending at index i with difference d.
        dp = [{} for _ in range(n)]
        best = 2

        for i in range(1, n):
            for j in range(i):
                d = nums[i] - nums[j]

                # If no earlier sequence has this difference, nums[j]
                # and nums[i] form a new sequence of length 2.
                length = dp[j].get(d, 1) + 1
                dp[i][d] = max(dp[i].get(d, 0), length)
                best = max(best, dp[i][d])

        return best

Time complexity: \(O(n^2)\).

Space complexity: \(O(n^2)\).

Comment on my solution¶

The idea of tracking lengths by tail and difference is close, but the implementation has several correctness issues:

It modifies a dictionary while iterating over its keys, which can raise RuntimeError.
It creates a difference-zero sequence of length 2 when processing the first occurrence of a value.
It checks whether x - d is a known tail but does not verify that its dictionary contains d.
It reads xx[d] before ensuring that key exists, which can raise KeyError.
Deleting prev_x_tail[d] discards states that may be needed by later elements.
The artificial infinite-difference state complicates the recurrence; treating every pair as length 2 is simpler.

# Ideas
# - different arithmetic subseqs can pass by the same number
#   - [1,2,3,5,7]
#     1 2 3
#       1 3 5 7
# - 0 <= nums[i] <= 500, i.e. small
#   - so maybe dp on the common difference
# - we can consider each number as the tail of an arithmetic subseqs
#   - we keep them in a dictionary
#   - we map them to a dictionary
#     - that map common diff -> length
# - every new element processed can be the start of a new subsequences

# WRONG
class Solution:
    def longestArithSeqLength(self, nums: list[int]) -> int:
        n = len(nums)
        tails = {} # tail -> {common diff -> length}
        best = 0
        for x in nums:
            tails.setdefault(x, {float("inf"): 1})
            for tail in tails:
                for d in tails[tail].keys():
                    if x - d in tails:
                        prev_x_tail = tails[x - d]
                        xx = tails.setdefault(x, {})
                        xx[d] = max(prev_x_tail[d] + 1, xx[d])
                        del prev_x_tail[d]
                        best = max(best, xx[d])
                new_d = x - tail
                if new_d not in tails[x]:
                    tails[x][new_d] = 2
        return best