Leetcode Problem 1218. Longest Arithmetic Subsequence of Given Difference

1218. Longest Arithmetic Subsequence of Given Difference

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize an empty hash map dp to store the maximum length of an arithmetic subsequence ending with each element.
  2. Set answer to 1, which is the minimum length of any subsequence.
  3. Iterate over each element arr[i] in the array.
  4. Calculate before_a as the length of the longest subsequence ending with arr[i] - difference.
    • If arr[i] - difference is in dp, before_a = dp[arr[i] - difference].
    • Otherwise, before_a = 0.
  5. Update dp[arr[i]] to before_a + 1.
  6. Update answer to the maximum of answer and dp[arr[i]].
  7. After iterating through the array, return answer.
UML Thumbnail

Brute Force Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...