题目

难度：★★★☆☆
类型：数组
方法：动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

示例 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位有符号整数。

解答

最长递增子序列的问题常常使用动态规划来解决。回顾一下如何求最长递增子序列的长度的问题。我们准备一个长度为len(nums)的数组length，其中length[i]表示以nums[i]为结尾元素的最长递增子序列的长度，初始状态填充为1。

需要进行两次遍历，外层循环的下标i从0到len(nums)，内层循环的下标j从0到i，这里也就保证了j<i，每当遇到nums[j]<nums[i]时，说明以nums[j]结尾的递增子序列（任意一个）有条件将nums[i]吸纳进去，并壮大自己的力量，使本递增子序列的长度增加1，用代码来表示也就是length[i] = max(length[i],length[j]+1)，表达的含义就是以nums[i]结尾的最长子序列的长度在以nums[j]结尾的最长子序列的长度的基础上增加nums[i]这个元素。

如果需要统计个数，我们准备一个新的数组count，并初始化为1，用来记录以nums[i]结尾的最长上升子序列的个数，例如上面描述的每当遇到nums[j]<nums[i]，更新长度向量的同时还要更新count向量，由于nums[i]相当于以nums[j]结尾的最长序列的一个向外扩展，因此直接继承nums[j]结尾的最长子序列的个数即可，也就是count[i]=count[j]。

但是，只有继承是远远不够的，在合适的时候还需要进行更新。这里需要说明一下的是，lenght向量中任意一个位置，是有可能被更新多次的，如果length[i]处已经有值，它被覆盖的条件是有更大的值的出现。如果我们得到的length[j]+1正好和这个位置处的值lenght[i]相等说明什么呢？说明的是以nums[i]结尾的最长上升子序列在本次更新之前已经出现过了，出现的次数存在count[i]位置处，为了表达这种出现的重复，我们将以nums[j]结尾的最长上升子序列的出现次数和上一次的出现次数累加，并更新到count[i]位置就好了，这是这道题的难点。

最终返回的是出现长度最长的子序列出现的次数，如果python不熟可以查一下资料理解代码。

class Solution(object):
    def findNumberOfLIS(self, nums):
        N = len(nums)
        if N <= 1:
            return N
        length = [1] * N
        count = [1] * N

        for i, num in enumerate(nums):
            for j in range(i):
                if nums[j] < nums[i]:
                    if length[j] >= length[i]:
                        length[i] = max(length[i], 1 + length[j])
                        count[i] = count[j]
                    elif length[j] + 1 == length[i]:
                        count[i] += count[j]

        longest = max(length)
        return sum(c for i, c in enumerate(count) if length[i] == longest)

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析