> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/shu-zu/673-zui-chang-di-zeng-zi-xu-lie-de-ge-shu.md).

# \[673]\[中等]\[动态规划]\[贪心] 最长递增子序列的个数

## 题目描述

[673. 最长递增子序列的个数](https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/)

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

```
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
```

示例 2:

```
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
```

注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

## 解题思路

### 动态规划

以[\[300\]\[中等\]\[贪心\]\[二分\]\[动态规划\]\[树状数组\] 最长上升子序列](broken://pages/-MDHljisT5A9hSzWwpAt)为基础, 对于位置`i`,我们不仅要维护以`nums[i]`结尾的最长递增序列的长度`length[i]`, 还要知道改最长序列所有可能的数量`count[i]`.

对于`i`后的位置`j`, 如果有`nums[i] < nums[j]`, 则`nums[j]`可以组成新的上升序列. 还是从`0`到`j - 1`遍历所有位置, 判断`nums[j]`是否更大. `length[j]`的取其中的最大, `count[j]`则记录这个最大值对应的可能组合的累计, 如果遍历过程中遇到了更长的上升子序列, 更新`length[j]`的同时, `count[j]`重置为对应的产生更大序列的`count[i]`, 重新计数.

```python
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0

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

        max_len = max(length)
        return sum([count[i] for i, t_len in enumerate(length) if t_len == max_len])
```

### 贪心 + 二分

[一步一步推导出最优解法（2）- 最长递增序列个数](https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/solution/yi-bu-yi-bu-tui-dao-chu-zui-you-jie-fa-2-zui-chang/)

[\[300\]\[中等\]\[贪心\]\[二分\]\[动态规划\]\[树状数组\] 最长上升子序列](broken://pages/-MDHljisT5A9hSzWwpAt)中的**贪心+二分**方法, 使用一个长度为最终最长递增子序列长度的数组, 记录了**每个长度对应的所有递增子序列中, 末尾数字的最小值**. 本题中, 还是使用这种套路, 但记录的内容更复杂了. 详情参考上面的题解答案.

```python
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0

        length = []
        count = []
        for num in nums:
            index1 = bisect.bisect_left([t[0] for t in length], num)
            if index1 == len(length):
                if len(length) == 0:
                    length.append([num])
                    count.append([1])
                else:
                    last_length = length[-1]
                    last_count = count[-1]
                    index2 = bisect.bisect_left(last_length, num)
                    length.append([num])
                    count.append([last_count[0] - (last_count[index2] if index2 < len(last_count) else 0)])
            else:
                if index1 == 0:
                    length0 = length[0]
                    count0 = count[0]
                    length0.insert(0, num)
                    count0.insert(0, len(length0))
                else:
                    t_length = length[index1 - 1]
                    t_count = count[index1 - 1]
                    index2 = bisect.bisect_left(t_length, num)
                    t1 = t_count[0] - (t_count[index2] if index2 < len(t_count) else 0)
                    length[index1].insert(0, num)
                    count[index1].insert(0, t1 + count[index1][0])
        return count[-1][0]
```