Leetcode Problem 2915. Length of the Longest Subsequence That Sums to Target

2915. Length of the Longest Subsequence That Sums to Target

Leetcode Solutions

Dynamic Programming -D Array Optimization

  1. Initialize a 1D DP array dp of size target + 1 with all elements set to 0.
  2. Iterate over each number in nums.
  3. For each number, iterate backwards over the DP array from target - 1 down to the number itself.
  4. If dp[j] is not zero (indicating a subsequence of length dp[j] sums up to j), and j + nums[i] is less than or equal to target, update dp[j + nums[i]] to be the maximum of its current value and dp[j] + 1.
  5. After processing all numbers, if dp[target] is zero, return -1, indicating no subsequence sums up to target. Otherwise, return dp[target].
UML Thumbnail

Recursion with Memoization

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...