1027. Longest Arithmetic Subsequence

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Recall that a subsequence of an array nums is a list nums[i1], nums[i2], …, nums[ik] with 0 <= i1 < i2 < … < ik <= nums.length - 1, and that a sequence seq is arithmetic if seq[i+1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size(), res = 0;
        vector<vector<int>> dp(n, vector<int>(1001, 0));
        unordered_map<int, int> counter;
        for(int i = 0; i < n; i++) {
            for(auto [value, index] : counter) {
                int diff = nums[i] - value + 500;
                res = max(res, dp[i][diff] = max(dp[index][diff] + 1, dp[i][diff]));
            }
            counter[nums[i]] = i;
        }
        return res + 1;
    }
};