Leetcode Problem 673. Number of Longest Increasing Subsequence

673. Number of Longest Increasing Subsequence

Leetcode Solutions

Bottom-up Dynamic Programming

  1. Initialize two arrays length and count of size n with all elements set to 1.
  2. Iterate over the array with index i from 0 to n - 1.
    • For each i, iterate with index j from 0 to i - 1.
      • If nums[j] < nums[i], check if length[j] + 1 > length[i].
        • If true, update length[i] to length[j] + 1 and set count[i] to count[j].
        • Else if length[j] + 1 == length[i], add count[j] to count[i].
  3. Find the maximum value in length array, denote it as maxLength.
  4. Initialize result to 0.
  5. Iterate over the array with index i from 0 to n - 1.
    • If length[i] == maxLength, add count[i] to result.
  6. Return result.
UML Thumbnail

Top-down Dynamic Programming (Memoization)

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...