首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >《剑指offer》第28天:最长上升子序列(高频)

《剑指offer》第28天:最长上升子序列(高频)

作者头像
程序员小浩
发布于 2020-09-14 09:06:00
发布于 2020-09-14 09:06:00
48800
代码可运行
举报
文章被收录于专栏:小浩算法小浩算法
运行总次数:0
代码可运行

01、题目分析

第300题:最长上升子序列

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4

说明:

可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可

02、题目图解

首先我们分析题目,要找的是最长上升子序列(Longest Increasing Subsequence,LIS)。因为题目中没有要求连续,所以 LIS可能是连续的,也可能是非连续的。 同时,LIS符合可以从其子问题的最优解来进行构建的条件。所以我们可以尝试用动态规划来进行求解。首先我们定义状态:

dp[i] :表示以nums[i]结尾的最长上升子序列的长度

我们假定nums为[1,9,5,9,3],如下图:

我们分两种情况进行讨论:

  • 如果nums[i]比前面的所有元素都小,那么dp[i]等于1(即它本身)(该结论正确)
  • 如果nums[i]前面存在比他小的元素nums[j],那么dp[i]就等于dp[j]+1(该结论错误,比如nums[3]>nums[0],即9>1,但是dp[3]并不等于dp[0]+1)

我们先初步得出上面的结论,但是我们发现了一些问题。**因为dp[i]前面比他小的元素,不一定只有一个!**

可能除了 nums[j],还包括 nums[k],nums[p] 等等等等。所以 dp[i] 除了可能等于 dp[j]+1,还有可能等于 dp[k]+1,dp[p]+1 等等等等。所以我们求 dp[i],需要找到 dp[j]+1,dp[k]+1,dp[p]+1 等等等等 中的最大值。(我在3个等等等等上都进行了加粗,主要是因为初学者非常容易在这里摔跟斗!这里强调的目的是希望能记住这道题型!) 即:

dp[i] = max(dp[j]+1,dp[k]+1,dp[p]+1,.....) 只要满足: nums[i] > nums[j] nums[i] > nums[k] nums[i] > nums[p] ....

最后,我们只需要找到dp数组中的最大值,就是我们要找的答案。

分析完毕,我们绘制成图:

03、Go语言示例

根据以上分析,可以得到代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
func lengthOfLIS(nums []int) int {
 if len(nums) < 1 {
  return 0
 }
 dp := make([]int, len(nums))
 result := 1
 for i := 0; i < len(nums); i++ {
  dp[i] = 1
  for j := 0; j < i; j++ {
   if nums[j] < nums[i] {
    dp[i] = max(dp[j]+1, dp[i])
   }
  }
  result = max(result, dp[i])
 }
 return result
}

func max(a, b int) int {
 if a > b {
  return a
 }
 return b
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-09-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 小浩算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
漫画:动态规划系列 第三讲
在上一篇中,我们了解了什么是DP(动态规划),并且通过DP中的经典问题 "最大子序和",学习了状态转移方程应该如何定义。在本节中,我们将沿用之前的分析方法,通过一道例题,进一步巩固之前的内容!
程序员小浩
2020/03/31
3130
动态规划经典题之最长上升子序列
最长上升子序列(Longest Increasing Subsequence,LIS),在计算机科学上是指一个序列中最长的单调递增的子序列。
程序员小熊
2021/05/28
1K0
动态规划经典题之最长上升子序列
图解一道腾讯笔试算法题:「最长上升子序列」
今天分享的题目来源于 LeetCode 第 300 号问题:最长上升子序列。这道题在 腾讯 笔试中出现过 3 次。
五分钟学算法
2019/12/06
9900
【leetcode刷题】T165-最长上升子序列
https://leetcode-cn.com/problems/longest-increasing-subsequence/
木又AI帮
2019/09/17
4510
LeetCode-300-最长上升子序列
# LeetCode-300-最长上升子序列 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例 1: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升
benym
2022/07/14
1810
打卡群刷题总结0924——最长上升子序列
链接:https://leetcode-cn.com/problems/longest-increasing-subsequence
木又AI帮
2020/09/28
3080
leetcode刷题(65)——300. 最长上升子序列
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明:
老马的编程之旅
2022/06/22
1890
力扣300——最长上升子序列
这也是最基础的想法,利用递归,从每一个数开始,一个一个寻找,只要比选中的标准大,那么就以新的数为起点,继续找。全部找完后,找出最长的序列即可。
健程之道
2020/01/16
5360
干货:图解算法——动态规划系列
讲解动态规划的资料很多,官方的定义是指把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。概念中的各阶段之间的关系,其实指的就是状态转移方程。很多人觉得DP难(下文统称动态规划为DP),根本原因是因为DP区别于一些固定形式的算法(比如DFS、二分法、KMP),没有实际的步骤规定第一步第二步来做什么,所以准确的说,DP其实是一种解决问题的思想。
宜信技术学院
2020/03/06
8440
Leetcode 300. 最长上升子序列(n方dp,nlogn贪心+二分查找)
d[i]表示长度为i的末尾元素值,遍历一遍nums,遇到比当前d[len]元素大的就接在后面,否则就二分插入d[1~len]中的某个位置~
glm233
2020/09/28
5880
Leetcode 300. 最长上升子序列(n方dp,nlogn贪心+二分查找)
Leetcode 300. 最长上升子序列
申请等长的临时数组 arr,用于保存每个位置上对应的最长上升序列长度,则计算 arr[i] 时,需要遍历前 i 个位置,取 nums 值小于 nums[i] 的最大序列长度加一,即为 arr[i] 的值。
zhipingChen
2019/06/15
5580
动态规划:最长递增子序列
题目链接:https://leetcode-cn.com/problems/longest-increasing-subsequence/
代码随想录
2021/03/16
9270
动态规划:最长递增子序列
Java实现给定一个无序的整数数组,找到其中最长上升子序列的长度。
1 首先开辟一个新数组 ,长度等于nums //用来存储没一个值得最大上升子序列数目
编程张无忌
2021/01/26
9850
Java实现给定一个无序的整数数组,找到其中最长上升子序列的长度。
【一天一道Leetcode】最长递增子序列长度
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。
潘永斌
2021/03/09
1.1K0
LeetCode 300. 最长递增子序列
https://leetcode-cn.com/problems/longest-increasing-subsequence/
freesan44
2021/11/14
8360
LeetCode 300. 最长递增子序列
穿上衣服我就不认识你了?来聊聊最长上升子序列
最长上升子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长上升子序列。那么问题来了,它穿上衣服你还看得出来是么?
lucifer210
2020/06/29
7790
穿上衣服我就不认识你了?来聊聊最长上升子序列
动态规划入门看这篇就够了,万字长文!
今天是小浩算法 “365刷题计划” 动态规划 - 整合篇。大家应该期待已久了吧!奥利给!
程序员小浩
2020/05/08
1.7K0
动态规划入门看这篇就够了,万字长文!
LeetCode300. 最长上升子序列
 经典dp问题,用dp[i]表示前i+1个个数的最长上升子序列,也就是以ai为末尾的最长上升子序列长度,要注意的是dp初始化应该是1而不是0,因为对于每个数其本身就是一个长度为1的最长上升子序列
mathor
2018/07/24
7490
LeetCode300. 最长上升子序列
【DP】300. Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
echobingo
2019/06/14
5120
300. 最长递增子序列
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
名字是乱打的
2021/12/24
5680
相关推荐
漫画:动态规划系列 第三讲
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档