Longest Arithmetic Subsequence
Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.
A sequence is arithmetic if the difference between any two consecutive elements is the same.
Note: The subsequence does not need to be contiguous.
Examples
Input: [3,6,9,12]
Output: 4
Input: [9,4,7,2,10]
Output: 3
Hints
Start by considering all possible differences between elements in the array, as the arithmetic subsequence can have any common difference.
For each element at index `i`, and for each possible difference `d`, track the length of the longest arithmetic subsequence ending at `i` with difference `d` using a hash map (e.g., `dp[i][d]`).
To optimize, iterate through the array and for each element, check all previous elements to compute differences and update the DP state accordingly, ensuring you handle negative differences and overlapping subsequences efficiently.
Longest Arithmetic Subsequence
Given an array `nums` of integers, return the length of the longest arithmetic subsequence in `nums`.