452. Number of Longest Increasing Subsequence
You are given an integer array nums. Among all of its strictly increasing subsequences, some have the maximum possible length — count how many of them there are.
A subsequence keeps the original order but may skip elements. Two subsequences count separately whenever they use different index sets, even if the values they spell out are identical.
The function receives the array and returns one integer: the number of longest strictly increasing subsequences. The answer is guaranteed to fit in a 32-bit signed integer.
Example 1:
Input: nums = [1, 3, 5, 4, 7]
Output: 2
Explanation: The longest strictly increasing subsequences have length 4, and exactly two index sets achieve it: [1, 3, 5, 7] and [1, 3, 4, 7].
Example 2:
Input: nums = [2, 2, 2, 2, 2]
Output: 5
Explanation: Strictly increasing forbids equal neighbors, so no subsequence longer than one element exists. Each of the five single elements is a longest one.
Constraints:
- 1 ≤ nums.length ≤ 2000
- -10⁶ ≤ nums[i] ≤ 10⁶
- The answer fits in a 32-bit signed integer.
Hints:
The classic LIS recurrence tracks length[i] — the length of the longest increasing run ending at index i. Counting needs a partner array count[i]: how many distinct ways that best length can be achieved ending at i.
When you extend from j to i (nums[j] < nums[i]): a strictly longer run means count[i] restarts at count[j]; an equally long run means count[i] += count[j]. The final answer sums count[i] over every i whose length[i] equals the global maximum.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 3, 5, 4, 7]
Expected output: 2