#1218

Longest Arithmetic Subsequence of Given Difference

specialist · 800 · lc medium +31 · verified · 54.3% accepted · 3,376 likes · top 47%

Description

You have an integer array arr and an integer difference. Find the longest subsequence of arr that forms an arithmetic progression whose common difference equals exactly difference.

A subsequence is obtained by removing some (or no) elements from arr while preserving the relative order of the remaining elements.

Return the length of the longest such subsequence.

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].

Code

1

2

3

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int: