# \[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]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/shu-zu/673-zui-chang-di-zeng-zi-xu-lie-de-ge-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.