Number of Longest Increasing Subsequence
Medium · dynamic programming
Given a list of integers nums, count how many longest strictly increasing subsequences it has.
A subsequence keeps the original order but may skip elements. "Strictly increasing" means every chosen number is larger than the one before it. Two subsequences are different when they use different positions, even if they hold the same values. For example, in [2, 2, 3] the two subsequences [2, 3] (using the first 2 or the second 2) count separately.
Return how many subsequences reach the greatest possible length.
Examples
Example 1
Input: nums = [1, 3, 5, 4, 7]
Output: 2
The longest length is 4. The two choices are 1, 3, 5, 7 and 1, 3, 4, 7.
Example 2
Input: nums = [2, 2, 2, 2, 2]
Output: 5
No two equal numbers can follow each other, so the longest length is 1, and each of the five positions is its own subsequence.
Example 3
Input: nums = [4, 3, 2, 1]
Output: 4
Again the longest length is 1, and every position counts once.
Constraints
- 1 <= len(nums) <= 3000
- -10^6 <= nums[i] <= 10^6
- The answer fits in a signed 32-bit integer.