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).
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].
Constraints:
2 <= nums.length <= 10000 <= nums[i] <= 500Longest Arithmetic Subsequence - LeetCode
https://www.youtube.com/watch?v=Lm38EAoDc7c
This problem is similar to Longest Increasing Subsequence problem. The difference is that
we need to consider the arithmetic difference in this problem. How to keep track of the
length as well as the difference? We can use a hashmap, whose key is the difference and
value is the length. Then we can solve the problem with dynamic programming:
As noted in the problem description, 2 <= A.length, so we don't need to consider the edge
case when there is no element or only one element in A. The base case is A.length == 2,
then A itself is the longest arithmetic subsequence because any two numbers meet the
condition of arithmetic.
The optimization step is that for two elements A[i] and A[j] where j < i, the difference
between A[i] and A[j] (name it diff) is a critical condition. If the hashmap at position
j has the key diff, it means that there is an arithmetic subsequence ending at index j,
with arithmetic difference diff and length dp[j][diff]. And we just add the length by 1.
If hashmap does not have the key diff, then those two elements can form a 2-length
arithmetic subsequence. And update the result if necessary during the iteration.
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int n = nums.size();
if(n<=1)
return n;
int maxlen = 2;
vector<unordered_map<int,int>> dp(n);//each element of the array nums has their own map
// We can use a hashmap, whose key is the difference and
// value is the length
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
int diff = nums[i]-nums[j];
if(dp[j].find(diff)!=dp[j].end())
dp[i][diff] = 1 + dp[j][diff];
else
dp[i][diff] = 2;
maxlen = max(maxlen,dp[i][diff]);
}
}
return maxlen;
}
};