Longest Arithmetic Subsequence Of Given Difference - Leetcode Solution

The problem of finding the Longest Arithmetic Subsequence of Given Difference on LeetCode can be solved with a simple dynamic programming approach.

Given an array nums and a difference d, we need to find the length of the longest subsequence where the difference between any two consecutive numbers is equal to d.

To solve this problem, we can use a hash table (dictionary) to keep track of the length of the longest subsequence ending at each element in nums.

Here's the step-by-step solution:

1. Initialize a dictionary dp where dp[nums[i]] = 1, for all i.

2. Loop through each element in nums and update the value of dp[nums[i]] based on the value of dp[nums[i]-d].

   dp[nums[i]] = dp[nums[i]-d] + 1 if nums[i]-d is in dp else 1

The above step checks if the difference between nums[i] and nums[i]-d is equal to d. If it is, then we add 1 to the length of the longest subsequence ending at nums[i]-d to get the length of the longest subsequence ending at nums[i]. If nums[i]-d is not in dp, then the length of the longest subsequence ending at nums[i] is 1.

3. Return the maximum value in dp.

   return max(dp.values())

The above step returns the maximum value in dp, which represents the length of the longest subsequence with a difference of d.

Here's the complete code:

def longestSubsequence(nums, d): dp = {} for num in nums: dp[num] = 1 for num in nums: if num - d in dp: dp[num] = dp[num-d] + 1 return max(dp.values())

1