Number of Longest Increasing Subsequences
Implement findNumberOfLIS
Given an array of integers, count how many distinct strictly increasing subsequences share the maximum possible length — not just what that longest length is, but how many different ways it can be reached.
Extending the usual length table with a matching count table captures this directly: alongside dp[i], the length of the best increasing run ending at index i, keep how[i], the number of distinct subsequences that actually achieve that specific length at that index. Whenever an earlier, smaller element offers a strictly longer extension than anything found so far, index i's count resets to match that element's count, since a new best has been found. Whenever it only ties the current best length, that earlier element's count is folded in on top, because both routes are equally valid ways to reach the same length. Once every index carries its own length and count, the overall answer sums the counts of every index that reaches the longest length seen anywhere — since the true longest subsequence in the array may end at more than one position.
Example 1:
Input: nums = [2,4,6,5,8]
Output: 2
Example 2:
Input: nums = [6,6,6,6,6]
Output: 5
Example 3:
Input: nums = [1,2,4,3,5,4,7,2]
Output: 3
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 12 - ●
-1000 ≤ nums[i] ≤ 1000
nums =
[2, 4, 6, 5, 8]