写点什么

算法题每日一练:最长递增子序列

作者:知心宝贝
  • 2023-04-25
    江苏
  • 本文字数:908 字

    阅读完需:约 3 分钟

算法题每日一练:最长递增子序列

一、问题描述

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。


子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。


题目链接:最长递增子序列

二、题目要求

样例 1

输入: nums = [10,9,2,5,3,7,101]输出: 4解释: 最长递增子序列是 [2,3,7,101],因此长度为 4 。
复制代码

样例 2

输入: nums = [0,1,0,3,2,3]输出: 4
复制代码

考察

1.子序列、动态规划2.建议用时15~35min
复制代码

三、问题分析

对于这一道可以使用动态规划、二分查找解决,动态规划虽然执行用时多一些,但理解起来比较容易,所以用动态规划完成这一题。


还记得我们之前对于动态规划的三步走战略吗,之前的动态规划的力扣习题相当于入门,如果没有了解过动态规划,可以试着从这一篇入门题解开始做起:


算法题每日一练---第34天: 青蛙跳台阶开始做起。


还是用我们的三步走战略:

第一步 含义搞懂:

这是道一维的动态规划,其中 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]);


三步走,打完收工!

四、编码实现

class Solution {public:    int lengthOfLIS(vector<int>& nums) {        int i,j,n=nums.size(),dp[n+2],ans=0;//初始化变量        for(i=0;i<n;i++)//循环i        {            dp[i]=1;//变量初始            for(j=0;j<i;j++)//遍历i之前的数字            {                if(nums[j]<nums[i])//如果i比j对应的数据大                    dp[i]=max(dp[j]+1,dp[i]);//nums[i]加入大家庭            }            ans=max(ans,dp[i]);//寻找最大值        }        return ans;//返回结果    }};
复制代码

五、测试结果



发布于: 2023-04-25阅读数: 21
用户头像

知心宝贝

关注

公众号:穿越计算机的迷雾 2022-03-07 加入

生于尘埃 溺于人海 死于理想高台

评论

发布
暂无评论
算法题每日一练:最长递增子序列_数据结构_知心宝贝_InfoQ写作社区