This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

Topic describes

You are given an integer array arr and an integer difference, please find and return the length of the longest arithmetic subsequence in ARR, the difference between the adjacent elements of the subsequence is equal to difference.

A subsequence is a sequence derived from an ARR by removing some elements or none without changing the order of the rest of the elements.

  • Example 1:
Input: ARr = [1,2,3,4], difference = 1 Output: 4 Explanation: The longest arithmetic subsequence is [1,2,3,4].Copy the code
  • Example 2:
Input: arr = [1,3,5,7], difference = 1 Output: 1 Explanation: The longest arithmetic subsequence is any single element.Copy the code
  • 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].Copy the code
  • Tip:
-   `1 <= arr.length <= 105`
`-104 <= arr[i], difference <= 104`
Copy the code

Implementation approach

It is assumed that dy[I] is the last number of an arithmetic sequence, and the equation is: dy[I] = dy[i-1] + 1. It can be understood that the current number of dy[I] is equal to the length of the arithmetic sequence stored by the previous digit of the arithmetic sequence dy[i-1] plus 1. For example 1, the arithmetic sequence [1,2,3,4] stores 1 at the position of the number 1, and adds 1 to the value stored at the position of the number 2, so that the value stored at the position of the number 4 is 3+1=4.

Overall implementation process:

  1. Define res to record the length of the longest arithmetic sequence.
  2. Define map to store the length of arithmetic sequence ending with item.
  3. Iterate over the length of the arithmetic array stored in ARR to update res.
  4. Returns the res.
/ * * *@param {number[]} arr
 * @param {number} difference
 * @return {number}* /
var longestSubsequence = function(arr, difference) {
    let res = 1
    let map = new Map(a)for (let item of arr) {
        map.set(item, (map.get(item - difference) || 0) + 1) // Add 1 to the value stored in the preceding digit of the arithmetic column
        res = Math.max(res, map.get(item)) // Take the longest of the arithmetic sequences
    }
    return res
};
Copy the code