leecode题解Golang版本-300-最长递增子序列

前言

开设专栏主要是为了能够记录自己刷题过程中的所思所想,以便能够在未来开发工作中能够快速温习并应用。如果文章能够带给大家一些启发,那便是意外之喜了。

题目描述

leecode-300 最长递增子串
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

题解

func lengthOfLIS(nums []int) int {
   
	m := make([]int, len(nums))
	res := 0
	for i := 0; i < len(nums); i++ {
   
		counter := 1
		for j := 0; j < i; j++ {
   
			if nums[j] < nums[i] {
   
				counter = Max(counter, m[j]+1)
			}
		}
		m[i] = counter
		res = Max(res, counter)
	}
	return res

}
func Max(a, b int) int {
   
	if a > b {
   
		return a
	} else {
   
		return b
	}
}

核心:动态规划

首先,我们应该思考的是,对于序列中的某一个元素i而言,它的存在会对我们求解的结果有影响吗?以序列0316227为例,我们来分析解题思路:
在这里插入图片描述
如上图所示,以0为末尾的最长严格递增子序列是0,以3为末尾的最长子序列是03.我们来分析第三个元素1。当这个元素作为序列末尾的时候,他的最长递增子序列的长度我们该怎么计算。显而易见的是,0<1,3>1,我们是不是可以得出这样的结论,第三个元素1可以添加到第一个元素为末端的子序列的后边,这时的子序列为01,同样符合严格递增子序列的定义。我们可以叠加以第一个元素为末端的严格递增子序列的长度+1,就是以第三个元素为末端的递增子序列的长度。

在这里插入图片描述
我们将目光转移到第四个元素,6>1,6>3,6>0,那么以6可以添加到以0/3/1为末端的最长递增子序列的末端,以6为末端的最长递增子序列就是上面以0/3/1为末端的最长递增子序列中的最大值。依次类推,我们可以得出以下的求解过程:

在这里插入图片描述

上图的DP[i]指的是:以第i个元素为序列末端时的最长严格递增子序列长度。上图展示了该值的推导过程。当我们遍历得出DP[i]的值的时候,我们就可以推导该题的全部可能场景。原体中提及的一个整数数组 nums ,找到其中最长严格递增子序列的长度的题解,一定符合上文推导中提及的假设:即这个题解一定是以第i个元素为序列末端时的最长严格递增子序列长度,那么我求出DP[i]的最大值,就是我们最终的题解。

后记

算法学习,前路慢慢,与君共勉

无他,唯手熟尔

相关推荐

  1. LeetCode 300 递增序列

    2023-12-21 20:00:04       63 阅读
  2. Leetcode 300 递增序列

    2023-12-21 20:00:04       57 阅读
  3. LeetCode-300.递增序列

    2023-12-21 20:00:04       41 阅读
  4. LeetCode 300. 递增序列

    2023-12-21 20:00:04       41 阅读
  5. leetcode300递增序列

    2023-12-21 20:00:04       29 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-21 20:00:04       106 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-21 20:00:04       116 阅读
  3. 在Django里面运行非项目文件

    2023-12-21 20:00:04       95 阅读
  4. Python语言-面向对象

    2023-12-21 20:00:04       103 阅读

热门阅读

  1. Golang学习之路一二基础语法与变量

    2023-12-21 20:00:04       62 阅读
  2. 一种磁盘上循环覆盖文件策略

    2023-12-21 20:00:04       56 阅读
  3. Windows: office: MS word: 吐槽:怎么分割一个word文档

    2023-12-21 20:00:04       58 阅读
  4. Nginx conf文件配置

    2023-12-21 20:00:04       49 阅读
  5. 将 OpenLDAP 与 IBM Spectrum LSF 集成

    2023-12-21 20:00:04       41 阅读
  6. 【C语言】6-5 判断回文字符串 分数 20

    2023-12-21 20:00:04       57 阅读
  7. C++ opencv RGB三通道提升亮度

    2023-12-21 20:00:04       56 阅读
  8. 复习linux——sudo授权

    2023-12-21 20:00:04       60 阅读
  9. MyBatis-Plus 内置接口方法使用

    2023-12-21 20:00:04       62 阅读