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 &lt;= i1 &lt; i2 &lt; ... &lt; ik &lt;= nums.length - 1, and that a sequence seq is arithmetic if seq[i+1] - seq[i] are all the same value (for 0 &lt;= i &lt; seq.length - 1).

&nbsp;
Example 1:

Input: nums = [3,6,9,12]
Output: 4
Explanation: 
The whole array is an arithmetic sequence with steps of length = 3.


Example 2:

Input: nums = [9,4,7,2,10]
Output: 3
Explanation: 
The longest arithmetic subsequence is [4,7,10].


Example 3:

Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation: 
The longest arithmetic subsequence is [20,15,10,5].


&nbsp;
Constraints:


	2 &lt;= nums.length &lt;= 1000
	0 &lt;= nums[i] &lt;= 500


class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        dp = [[1]*1001 for i in range(len(nums))]
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                d = nums[j] - nums[i] + 500
                dp[j][d] = max(dp[i][d]+1,dp[j][d])
        return max([max(i) for i in dp])
class Solution 
{
    public int longestArithSeqLength(int[] nums) 
    {
        int n = nums.length;
        int longest = 0;
        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 diff = nums[i] - nums[j];
                dp[i].put(diff, dp[j].getOrDefault(diff, 1) + 1);
                longest = Math.max(longest, dp[i].get(diff));
            }
        }
        
        return longest;
    }
}
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        
        int n=size(nums);
        int ans=1;
        vector<vector<int>>  dp(n,vector<int>(1005,1));
        
        for(int i=1;i<n;i++) 
            for(int j=0;j<i;j++)
                ans=max(ans, dp[i][nums[i]-nums[j]+500]= 1+dp[j][nums[i]-nums[j] +500]);
             
        
        return ans;
        
    }
};
var longestArithSeqLength = function(nums) {
    if (nums === null || nums.length === 0) {
        return 0;
    }
    let diffMap = new Array(nums.length).fill(0).map(() => new Map());
    let maxLen = 1;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            let diff = nums[i] - nums[j];
            // if prev element has an ongoing arithmetic sequence with the same common difference
            // we simply add 1 to the length of that ongoing sequence, hence diffMap[j].get(diff) + 1
            // else, we start a new arithmetic sequence, initial length is 2
            diffMap[i].set(diff, diffMap[j].get(diff) + 1 || 2);
            maxLen = Math.max(maxLen, diffMap[i].get(diff));
        }
    }
    return maxLen;
    // T.C: O(N^2)
    // S.C: O(N^2)
};
Longest Arithmetic Subsequence