Longest Arithmetic Subsequence — DP + Hash Map per Index

Problem 185 · Longest Arithmetic Subsequence

Difficulty: Medium · Pattern: DP + HashMap per index

Find the length of the longest arithmetic subsequence in nums.

Intuition

dp[i] is a map from difference d to the longest subsequence ending at index i with common difference d. For each j < i, update dp[i][nums[i]-nums[j]] = dp[j].get(diff, 1) + 1.

Solutions

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

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

# Python
from collections import defaultdict
def longestArithSeqLength(nums):
    dp = [defaultdict(int) for _ in nums]
    ans = 2
    for i in range(1, len(nums)):
        for j in range(i):
            d = nums[i] - nums[j]
            dp[i][d] = dp[j].get(d, 1) + 1
            ans = max(ans, dp[i][d])
    return ans

Complexity

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