1027. Longest Arithmetic Subsequence
Description
Given an array nums
of integers, return the length of the longest arithmetic subsequence in nums
.
Note that:
- A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
- A sequence
seq
is arithmetic ifseq[i + 1] - seq[i]
are all the same value (for0 <= 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 <= 1000
0 <= nums[i] <= 500
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ as the maximum length of the arithmetic sequence ending with $nums[i]$ and having a common difference of $j$. Initially, $f[i][j]=1$, that is, each element itself is an arithmetic sequence of length $1$.
Since the common difference may be negative, and the maximum difference is $500$, we can uniformly add $500$ to the common difference, so the range of the common difference becomes $[0, 1000]$.
Considering $f[i]$, we can enumerate the previous element $nums[k]$ of $nums[i]$, then the common difference $j=nums[i]-nums[k]+500$, at this time $f[i][j]=\max(f[i][j], f[k][j]+1)$, then we update the answer $ans=\max(ans, f[i][j])$.
Finally, return the answer.
If initially $f[i][j]=0$, then we need to add $1$ to the answer when returning the answer.
The time complexity is $O(n \times (d + n))$, and the space complexity is $O(n \times d)$. Where $n$ and $d$ are the length of the array $nums$ and the difference between the maximum and minimum values in the array $nums$, respectively.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|