1218. Longest Arithmetic Subsequence of Given Difference
Description
Given an integer array arr
and an integer difference
, return the length of the longest subsequence in arr
which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference
.
A subsequence is a sequence that can be derived from arr
by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: arr = [1,2,3,4], difference = 1 Output: 4 Explanation: The longest arithmetic subsequence is [1,2,3,4].
Example 2:
Input: arr = [1,3,5,7], difference = 1 Output: 1 Explanation: The longest arithmetic subsequence is any single element.
Example 3:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2 Output: 4 Explanation: The longest arithmetic subsequence is [7,5,3,1].
Constraints:
1 <= arr.length <= 105
-104 <= arr[i], difference <= 104
Solutions
Solution 1: Dynamic Programming
We can use a hash table $f$ to store the length of the longest arithmetic subsequence ending with $x$.
Traverse the array $\textit{arr}$, and for each element $x$, update $f[x]$ to be $f[x - \textit{difference}] + 1$.
After the traversal, return the maximum value in $f$ as the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{arr}$.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|