1218. Longest Arithmetic Subsequence of Given Difference

Difficulty: 中等

Given an integer array arr and an integer <font face="monospace" style="display: inline;">difference</font>, 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.

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

Solution

Language: Python3

​class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dict_arr={}
        rep=0
        for num in arr:
            if num-difference not in dict_arr:
                dict_arr[num]=1
            else:
                dict_arr[num]=1+dict_arr[num-difference]
            rep=max(rep,dict_arr[num])
        return rep

Solution

Language: Python3

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dict_arr={}
        for k in range(len(arr)):
            if arr[k] not in dict_arr:
                dict_arr[arr[k]]=[k]
            else:
                dict_arr[arr[k]].append(k)
        
        rep=0
        used_num=set()
        
        for k in range(len(arr)):
            if arr[k] in used_num:
                continue
                
            used_num.add(arr[k])
            cnt=1
            cur=arr[k]
            loc=k
            while cur+difference in dict_arr and dict_arr[cur+difference][-1]>loc:
                used_num.add(cur+difference)
                cnt+=1
                loc=self.searchMinLocLargerThenK(dict_arr[cur+difference],loc)
                cur+=difference
            rep=max(rep,cnt)
        return rep
    
    def searchMinLocLargerThenK(self,nums,k):
        l,r=0,len(nums)-1
        while l<=r:
            mid=(l+r)//2
            if nums[mid]>k:
                r=mid-1
            else:
                l=mid+1
        return nums[l]