34-Longest-Arithmetic-Subsequence.md

Longest Arithmetic Subsequence

Problem Link

https://leetcode.com/problems/longest-arithmetic-subsequence/

---

Pattern

• Dynamic Programming

---

Approach

Use HashMap to track longest arithmetic subsequence ending at each element with specific difference.

---

Time Complexity

O(n^2)

Space Complexity

O(n^2)

---

Java Solution

import java.util.*;
class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length, ans = 2;
        List<Map<Integer, Integer>> dp = new ArrayList<>();
        for (int i = 0; i < n; i++) dp.add(new HashMap<>());
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                dp.get(i).put(diff, dp.get(j).getOrDefault(diff, 1) + 1);
                ans = Math.max(ans, dp.get(i).get(diff));
            }
        }
        return ans;
    }
}