[1218. Longest Arithmetic Subsequence of Given Difference](https://leetcode.com/problems/find-eventual-safe-states/)

### 題目描述

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` <= 10^5^
* -10^4^ <= `arr[i]`, `difference` <= 10^4^

### 解答
#### C++

class Solution {
public:
    int longestSubsequence(vector<int>& nums, int diff) {
        int n = nums.size();
        int ans = 1;
        unordered_map<int, int> seen;
        seen[nums[0]] ++;
        for (int i = 1; i < nums.size(); i ++) {
            seen[nums[i]] = seen.count(nums[i] - diff) ? 1 + seen[nums[i] - diff] : 1;
            ans = max(ans, seen[nums[i]]);
        }
        return ans;
    }
};

> [name=Jerry Wu][time=14 July, 2023]

#### Python

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d = defaultdict(int)
        for n in arr:
            d[n] = d[n - difference] + 1
        return max(d.values())

> [name=Yen-Chi Chen][time=Sat, Jul 15, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)