hardDynamic Programming 1DPure DSA~40 min
Number of Longest Increasing Subsequences
Beyond the length of the longest increasing run of readings, count how many distinct longest increasing subsequences exist.
Problem
Given an integer array nums, return the number of longest strictly increasing subsequences. Two subsequences are different if they pick different index sets.
Input
An integer array nums.
Output
An integer: the count of longest increasing subsequences.
Constraints
- 1 <= nums.length <= 2000
- -10^6 <= nums[i] <= 10^6
- The answer fits in a 32-bit integer.
Examples
Example 1
Input
nums = [1,3,5,4,7]
Output
2
Both [1,3,4,7] and [1,3,5,7] have the maximum length 4.
Example 2
Input
nums = [2,2,2,2,2]
Output
5
The longest length is 1, achieved by each of the five elements.