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位有符号整数。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Top-down 这道题目是第300题的升级,那道题目仅要求找出最长递增子序列(LIS)的长度,而这道题目需要统计LIS有多少个。为了求出数组nums的LIS个数,我们先要求得最长递增子序列的长度maxLen。然后扫描nums数组,统计LIS长度为maxLen的个数。 首先我们实现一个函数,求数组nums的LIS的长度(参考300题的Top-down解法)。我们定义函数lengthOfLIS(int[] nums, int n),表示计算数组nums前n个元素(n从1开始,包含第n个且必须使用第n个元素)能够形成LIS的长度。例如我们有nums = [1,2,3,2,2],那么lengthOfLIS(nums, 4) = 2而不是3,因为我们必须使用nums[4]。 为了求num前n个元素的LIS,我们可以使用递归来解决。对于长度n,我们向前寻找某一元素i,使其满足nums[n] > nums[i](递增的定义),然后递归调用lengthOfLIS(nums, i),即求解nums数组前i个元素的LIS。代码如下: 下一步,我们定义函数count(int[] nums, int n)用于计算nums前n个元素(n从1开始,包含第n个且必须使用第n个元素)构成的LIS长度为maxLen的递增子序列数量。它会调用上面实现的函数lengthOfLIS(nums, n)。在这里我们举一个例子,nums = [1,3,2,4,5],则 count(nums,…

Read more