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

300. 最长上升子序列

题目描述 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。说明: 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗? 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/longest-increasing-subsequence著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – O(n^2) 这是一道经典的dp题目,大体上有两种解法,第一种是dp(时间复杂度O(n^2));第二种是dp+二分搜索(时间复杂度O(nlogn)),我们先介绍O(n^2)的解法。而第一种dp还可以分为Bottom-up和Top-down两种实现方式。 Bottom-up 我们定义数组dp[|nums|],dp[i]表示使用nums数组前i个元素且必须使用nums[i],能够构成的最长递增子序列的长度。那么有dp[i] = max(dp[j]) + 1, 其中nums[i] > nums[j], j < i,如果找不到这样的j,那么dp[i] = 1。 如果形象的描述算法的执行过程那就是使用双重循环,外循环使用变量i指向nums数组的每个元素,然后内循环用变量j扫描0~i。当nums[i] > nums[j]时,更新prev = max(prev, dp[j])。当内层循环扫描完毕,更新dp[i] = perv + 1。当双重循环执行完毕,dp数组中的最大值就是nums的最长递增子序列。 Top-down 自顶向下的思路使用递归来实现,我们定义一个辅助函数LIS(nums, curr),表示从nums数组的前curr个元素(包含curr)寻找LIS,并返回LIS的长度。那么我们需要利用更小的子问题求解当前问题,所以在for循环中又递归调用LIS。 为了避免重复求解,我们使用数组int[] cache记录求解过问题的答案。现在我们只需要循环的调用LIS函数,将各种问题的规模都交给LIS函数来求解,最大值就是数组nums的LIS。 全部代码如下: 解法2 – O(nlogn) 解法2是一个神奇的解法,我们一边读取nums数组,一边维护一个由nums形成的递增子序列 –…

Read more