673. 最长递增子序列的个数(Medium)

题目描述

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

样例

Input: nums = [1,3,5,4,7]
Output: 2

题解

算是 300. 最长递增子序列 的变形把，只是需要把 max(dp[i], dp[j] + 1) 分开讨论

代码示例

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        length = [1] * n
        count = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]: # 严格递增
                    # length[i] = max(length[i], length[j] + 1) 
                    # 上面是求最长子序列的转移方程, 等价于
                    # if length[j] + 1 >= length[i]: <--- 这个要拆分开使用
                    #      length[i] = length[j] + 1
                    if length[j] + 1 == length[i]: # 相等长度的方案，添加一下
                        count[i] += count[j] # 添加新方案
                    elif length[j] + 1 > length[i]: # 更新最长子串
                        length[i] = length[j] + 1
                        count[i] = count[j] 
        maxLength = max(length)
        return sum([ c for l, c in zip(length, count) if l == maxLength])