Number of Longest Increasing Subsequence
Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Examples
Input: [1,3,5,4,7]
Output: 2
Input: [2,2,2,2,2]
Output: 5
Hints
Use dynamic programming to track two arrays: `lengths[i]` (length of LIS ending at `i`) and `counts[i]` (number of LIS ending at `i`).
For each `i`, iterate through all `j < i` where `nums[j] < nums[i]`. If `lengths[j] + 1 > lengths[i]`, update `lengths[i]` and set `counts[i] = counts[j]`. If equal, add `counts[j]` to `counts[i]`.
After processing all elements, find the maximum value in `lengths` and sum all `counts[i]` where `lengths[i]` equals this maximum.
Number of Longest Increasing Subsequence
Given an integer array `nums`, return the number of longest increasing subsequences.