# 673. Number of Longest Increasing Subsequence

#### Medium

***

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 longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
```

 

**Constraints:**

* `1 <= nums.length <= 2000`
* `-106 <= nums[i] <= 106`

`Solution is exactly same as Problem 300 : Longest Increasing Subsequence`

```python
class Solution:
    def findNumberOfLIS(self, nums):
        if not nums: 
            return 0
        decks, ends_decks, paths = [], [], []
        for num in nums:
            deck_idx = bisect.bisect_left(ends_decks, num)
            n_paths = 1
            # print('Deck id', deck_idx)
            if deck_idx > 0:
                l = bisect.bisect(decks[deck_idx-1], -num)
                n_paths = paths[deck_idx-1][-1] - paths[deck_idx-1][l]
            # print("n Paths", n_paths)
            if deck_idx == len(decks):
                decks.append([-num])
                ends_decks.append(num)
                paths.append([0,n_paths])
            else:
                decks[deck_idx].append(-num)
                ends_decks[deck_idx] = num
                paths[deck_idx].append(n_paths + paths[deck_idx][-1])
            # print(decks)
            # print(paths)
            # print(ends_decks)
            # print("="*10)
        return paths[-1][-1]
```