1218. Longest Arithmetic Subsequence of Given Difference

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`

1218. Longest Arithmetic Subsequence of Given Difference
``````struct Solution;
use std::collections::HashMap;

impl Solution {
fn longest_subsequence(arr: Vec<i32>, difference: i32) -> i32 {
let mut hm: HashMap<i32, usize> = HashMap::new();
let mut res = 0;
for x in arr {
let prev = if let Some(&size) = hm.get(&(x - difference)) {
size
} else {
0
};
let count = hm.entry(x).or_default();
*count = (*count).max(prev + 1);
res = res.max(*count);
}
res as i32
}
}

#[test]
fn test() {
let arr = vec![1, 2, 3, 4];
let difference = 1;
let res = 4;
assert_eq!(Solution::longest_subsequence(arr, difference), res);
let arr = vec![1, 3, 5, 7];
let difference = 1;
let res = 1;
assert_eq!(Solution::longest_subsequence(arr, difference), res);
let arr = vec![1, 5, 7, 8, 5, 3, 4, 2, 1];
let difference = -2;
let res = 4;
assert_eq!(Solution::longest_subsequence(arr, difference), res);
}
``````