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.

Example 1:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

Constraints:

• 1 <= nums.length <= 2000
• -10^6 <= nums[i] <= 10^6
• The answer is guaranteed to fit inside a 32-bit integer.

## Number of Longest Increasing Subsequences

This problem asks us to find the number of longest increasing subsequences in a given integer array. A strictly increasing subsequence is a sequence of elements from the array such that each element is greater than the previous one, and we want to find the count of such sequences that have the maximum possible length.

### Naive Approach (Brute Force)

A brute-force approach would involve generating all possible subsequences, checking if they are increasing, and keeping track of the longest increasing subsequence(s) and their count. This approach has exponential time complexity and is not practical for larger input sizes.

### Optimal Approach (Dynamic Programming)

We can use dynamic programming to solve this problem efficiently. We maintain two arrays:

1.  `length[i]`: The length of the longest increasing subsequence ending at index `i`.
2.  `count[i]`: The number of longest increasing subsequences ending at index `i`.

We iterate through the `nums` array, and for each element `nums[i]`, we compare it with all previous elements `nums[j]` (where `j < i`). If `nums[i] > nums[j]`, it means we can extend the increasing subsequence ending at `j` by including `nums[i]`. We update `length[i]` and `count[i]` based on the following conditions:

*   If `length[j] + 1 > length[i]`: We found a longer increasing subsequence ending at `i`. Update `length[i]` to `length[j] + 1` and `count[i]` to `count[j]` (since the number of subsequences ending at `i` is now the same as the number of subsequences ending at `j`).
*   If `length[j] + 1 == length[i]`: We found another increasing subsequence of the same length ending at `i`. Add `count[j]` to `count[i]` (since we have additional subsequences of the same length).

After iterating through all elements, we find the maximum length in the `length` array and sum the counts for all indices with that maximum length. This sum gives us the number of longest increasing subsequences.

```python
def findNumberOfLIS(nums):
    n = len(nums)
    if n <= 1:
        return n

    length = [1] * n
    count = [1] * n

    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j]:
                if length[j] + 1 > length[i]:
                    length[i] = length[j] + 1
                    count[i] = count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]

    max_len = max(length)
    ans = 0
    for i in range(n):
        if length[i] == max_len:
            ans += count[i]

    return ans

Example Usage:

nums1 = [1, 3, 5, 4, 7]
print(findNumberOfLIS(nums1))  # Output: 2

nums2 = [2, 2, 2, 2, 2]
print(findNumberOfLIS(nums2))  # Output: 5

Time Complexity Analysis

The time complexity is O(n^2), where n is the length of the input array nums. This is because we have two nested loops. The outer loop iterates through each element of nums, and the inner loop iterates through all the elements before the current element.

Space Complexity Analysis

The space complexity is O(n), where n is the length of the input array nums. This is because we use two arrays, length and count, each of size n, to store the length and count of the longest increasing subsequences ending at each index.

Edge Cases

1. Empty array: If the input array is empty, the length of the longest increasing subsequence is 0, and the number of such subsequences is also 0.
2. Array with one element: If the input array has only one element, the length of the longest increasing subsequence is 1, and the number of such subsequences is 1.
3. Array with all equal elements: If the input array contains all equal elements, the length of the longest increasing subsequence is 1, and the number of such subsequences is equal to the length of the array.
4. Array in descending order: If the input array is in descending order, the length of the longest increasing subsequence is 1, and the number of such subsequences is equal to the length of the array.