【leetcode】300.最长递增子序列
leetcode刷题笔记-300.最长递增子序列。
题目
https://leetcode.cn/problems/longest-increasing-subsequence/description/
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
1 | 示例 1: |
提示
1 | 1 <= nums.length <= 2500 |
思路
先理解题目说的两个概念
- 严格递增:
[1,2,3,4]
是严格递增,[1,2,2,3]
不是严格递增; - 子序列:数组中的一部分,删除某些元素后得到的序列,比如
[1,2,3]
数组,删除2后可以得到子序列1,3
,也可以不删除元素1,2,3
也是它的子序列。但是3,1
或者2,1
都不是这个数组的子序列,因为元素的顺序和源数组中元素的顺序不一致;
了解定义了,就可以上动态规划的思路了。
我们定义dp数组的含义为源数组中下标i和i之前的最长递增子序列的长度(这一点和第五题最长回文子串的思路类似)。易得dp数组应该全部初始化为1,即认为最开始的时候,每一位之前的最长递增子序列是他自己。
那么递推方程应该是咋样的呢?分为两种情况
- 当前位元素大于前一位,那么当前的最长子序列长度应该是前一位的最长子序列长度+1;
- 当前位元素小于前一位,说明不能沿用之前的结果,当前的最长子序列长度得保持不变;
可得递推公式dp[i] = max(dp[i], dp[j] + 1)
,判断逻辑如下
1 | if(nums[i] > nums[i-1]){ |
但是这样判断还不够,因为子序列是允许删除某些元素的,对于遍历一个数组而言,它就是允许遍历不连续,所以我们需要用两层循环来处理,外层循环i从1开始遍历nums数组(从0开始没有意义),内层循环j从0开始遍历到i-1。
1 | for(int i = 1;i<nums.size();i++){ |
为什么我们需要用max来计算呢?因为每一次对i的递推都需要遍历i之前的所有元素才能递推出来,可能会出现前面某一位的最长递增子序列结果更大的情况,我们必须要保证得到的是最长的那一个子序列值。
同时,我们的遍历是从左往右的,当遍历到i的时候,i之前的那些元素在dp里面已经被正常计算出来最长的子序列长度了,所以我们只需要判断一次nums[i] > nums[j]
,就可以沿用之前的结果了。
完整代码
现在就可以写最终的代码了
1 | class Solution { |
时间复杂度是O(n^2)
,空间复杂度是O(n)
。
和这道题类似的是 674. 最长连续递增序列,其中要求子序列必须是连续的,中间不能中断。我会在另外一篇博客中写674的题解。