Leetcode Problem 446. Arithmetic Slices II - Subsequence

446. Arithmetic Slices II - Subsequence

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a variable result to 0 to store the final count of arithmetic subsequences.
  2. Create a dictionary dp where dp[i] is another dictionary that maps a common difference d to the number of weak arithmetic subsequences ending at index i with difference d.
  3. Iterate over the array using two nested loops with indices i and j where i goes from 1 to len(nums) - 1 and j goes from 0 to i - 1.
  4. For each pair (i, j), calculate the difference d = nums[i] - nums[j].
  5. If d is not in dp[i], initialize dp[i][d] to 0.
  6. Add dp[j].get(d, 0) + 1 to dp[i][d]. The get method is used to handle the case when d is not in dp[j].
  7. Add dp[j].get(d, 0) to result because these are the number of new arithmetic subsequences formed by adding nums[i].
  8. After the loops, return result as the final 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...