算法题每日一练:最长递增子序列
一、问题描述
给你一个整数数组 nums
,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
题目链接:最长递增子序列。
二、题目要求
样例 1
复制代码
样例 2
复制代码
考察
复制代码
三、问题分析
对于这一道可以使用动态规划、二分查找解决,动态规划虽然执行用时多一些,但理解起来比较容易,所以用动态规划完成这一题。
还记得我们之前对于动态规划的三步走战略吗,之前的动态规划的力扣习题相当于入门,如果没有了解过动态规划,可以试着从这一篇入门题解开始做起:
还是用我们的三步走战略:
第一步 含义搞懂:
这是道一维的动态规划,其中 dp[i]就代表第 i 个下标为终点的子序列最大长度。
第二步 变量初始:
变量初始的话,对于每一个 dp[i],最坏的情况就是前面的数字全部比i
大,那它就只能是孤零零的1
了。
第三步 规律归纳:
在确定 dp[i]的值之前,dp[0~i-1]的值我们应该都知道了。
定义j=i-1
那我们从 0~j 开始遍历,只要当前位置 nums[i]>nums[j],那我们就把 nums[i]加入 dp[j]的大家庭之中,
dp[i]=dp[j]+1;(加入的这个 1 就是 nums[i])。
规律这不就归纳出来了,因为 dp[i]一开始都初始化 1,只要 nums[i]>nums[j],那么我们比较一下大小就行了
dp[i]=max(dp[j]+1,dp[i]);
三步走,打完收工!
四、编码实现
复制代码
五、测试结果
版权声明: 本文为 InfoQ 作者【知心宝贝】的原创文章。
原文链接:【http://xie.infoq.cn/article/deeedf6f9257a408b5374f9ef】。文章转载请联系作者。
评论