专栏首页小浩算法《剑指offer》第28天:最长上升子序列(高频)

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

01、题目分析

第300题:最长上升子序列

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

示例:

输入: [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语言示例

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

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
}

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:动态规划系列 第二讲

    在上一篇文章中,我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中,我们将继续通过1道简单题型,进一步学习动态规划的思想。

    程序员小浩
  • 漫画:动态规划系列 第三讲

    在上一篇中,我们了解了什么是DP(动态规划),并且通过DP中的经典问题 "最大子序和",学习了状态转移方程应该如何定义。在本节中,我们将沿用之前的分析方法,通过...

    程序员小浩
  • 《剑指offer》第26天:最大子序和

    首先我们分析题目,一个连续子数组一定要以一个数作为结尾,那么我们可以将状态定义成如下:

    程序员小浩
  • 漫画:动态规划系列 第二讲

    在上一篇文章中,我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中,我们将继续通过1道简单题型,进一步学习动态规划的思想。

    程序员小浩
  • 每日算法系列【LeetCode 376】摆动序列

    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。

    godweiyang
  • 漫画:动态规划系列 第三讲

    在上一篇中,我们了解了什么是DP(动态规划),并且通过DP中的经典问题 "最大子序和",学习了状态转移方程应该如何定义。在本节中,我们将沿用之前的分析方法,通过...

    程序员小浩
  • 程序员面试金典 - 面试题 16.17. 连续数列(DP/分治)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/contiguous-sequence-lcci 著...

    Michael阿明
  • LeetCode 198. House Robber(DP)

    题意:给你一个数组表示一个街道,每个数字表示一个房子里有多少钱,你可以打劫获得这些钱,但是不能同时打劫相邻的房子,问你最多可以得到多少钱,

    ShenduCC
  • 【leetcode刷题】T170-组合总和 Ⅳ

    https://leetcode-cn.com/problems/combination-sum-iv/

    木又AI帮
  • Golang Leetcode 377. Combination Sum IV.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89089210

    anakinsun

扫码关注云+社区

领取腾讯云代金券