Longest Arithmetic Subsequence

medium dynamic programming hash map arithmetic

Problem

Given an array of integers nums, return the length of the longest arithmetic subsequence in nums. A subsequence keeps the relative order of elements but may delete some. A subsequence is arithmetic if the difference between every pair of consecutive elements is the same.

Inputnums = [9, 4, 7, 2, 10]

Output3

The longest arithmetic subsequence is [4, 7, 10] with common difference 3.

nums (comma-separated)

def longest_arith_seq_length(nums):
    dp = [{} for _ in range(len(nums))]
    best = 1
    for i in range(len(nums)):
        for j in range(i):
            d = nums[i] - nums[j]
            dp[i][d] = dp[j].get(d, 1) + 1
            best = max(best, dp[i][d])
    return best

function longestArithSeqLength(nums) {
  const dp = nums.map(() => new Map());
  let best = 1;
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      const d = nums[i] - nums[j];
      const len = (dp[j].get(d) || 1) + 1;
      dp[i].set(d, len);
      best = Math.max(best, len);
    }
  }
  return best;
}

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length, best = 1;
        Map<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                int d = nums[i] - nums[j];
                int len = dp[j].getOrDefault(d, 1) + 1;
                dp[i].put(d, len);
                best = Math.max(best, len);
            }
        }
        return best;
    }
}

int longestArithSeqLength(vector<int>& nums) {
    int n = nums.size(), best = 1;
    vector<unordered_map<int, int>> dp(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int d = nums[i] - nums[j];
            int len = (dp[j].count(d) ? dp[j][d] : 1) + 1;
            dp[i][d] = len;
            best = max(best, len);
        }
    }
    return best;
}

Explanation

We want the longest subsequence with a constant gap between neighbors, but unlike the fixed-difference version, the gap can be anything. The idea is to track, for each ending position, the best chain length for every possible common difference.

So dp[i] is a map from a difference d to the length of the longest arithmetic subsequence that ends at index i and uses step d.

For each pair j < i, we compute their gap d = nums[i] - nums[j]. The chain ending at i with this gap simply extends the chain ending at j with the same gap: dp[i][d] = dp[j].get(d, 1) + 1. If j had no such chain, we treat it as the single element (length 1) and add nums[i].

We keep the running maximum across all maps and return it.

Example: nums = [9,4,7,2,10]. The values 4, 7, 10 share difference 3, so the DP builds that chain up to length 3, the answer.

Time: O(n²) Space: O(n²)