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

题目描述

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

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

示例 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][中等][贪心][二分][动态规划][树状数组] 最长上升子序列为基础, 对于位置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], 重新计数.

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）- 最长递增序列个数

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

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]