当前位置：首页 > news >正文

可视化图解算法75：最长上升子序列(最长递增子序列)

news 2026/6/12 18:26:33

1.题目

描述

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,1]、[1,3,5] 则不是它的子序列。

我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 i 和 j 满足 i<j 且 arr_i ≥arr_j。

数据范围： 0≤n≤1000

要求：时间复杂度 O(n²)，空间复杂度 O(n)

示例1

输入：

[6,3,1,5,2,3,7]

返回值：

说明：

该数组最长上升子序列为 [1,2,3,7] ，长度为4

2. 题解思路

本题求解的是最长子序列，因此需要了解子序列与子串的区别。

子串和子序列是计算机科学中常见的两个概念，它们都与字符串或序列的部分内容有关，但存在明显的区别。
子串（Substring）
定义：子串是指原字符串中连续的一段字符组成的序列。换句话说，子串是从原字符串中选取的一个或多个相邻字符构成的新字符串。

特点：子串是连续的，即子串中的字符在原字符串中是连续排列的。子串的长度至少为1，也可以是整个原字符串（即原字符串本身也是它自己的子串）。空字符串（即不包含任何字符的字符串）在某些定义下也被视为任何字符串的子串，但这取决于具体的上下文和定义。

示例：在字符串"abcdefg"中，"abc"、"def"和"cde"都是合法的子串。

子序列（Subsequence）
定义：子序列是从原序列中任意选取若干个元素组成的新序列，且这些元素在新序列中的相对顺序与原序列相同，但是允许跳过某些元素。

特点：子序列不一定连续，即子序列中的元素在原序列中可以是不连续的。子序列可以为空，即不选取任何元素。子序列也可以包含原序列的所有元素（此时子序列就等于原序列自身）。

示例：在字符串"abcdefg"中，"aceg"、"adg"和"bdf"都是合法的子序列。

具体思路如下：

如果文字描述的不太清楚，你可以参考视频的详细讲解。

Python版本：https://www.bilibili.com/cheese/play/ep1375305
Java版本：https://www.bilibili.com/cheese/play/ep1368531
Golang版本：https://www.bilibili.com/cheese/play/ep1368731

3.编码实现

核心代码如下：

func LIS(arr []int) int {//特殊情况if len(arr) == 0 {return 0}//1.定义状态.	i：数组arr的下标; dp[i]：数组arr[0:i]区间内的最长递增子序列dp := make([]int, len(arr))//2.初始化边界条件：dp[i]=1，对于每一个元素来说，如果只有此元素本身，最长递增子序列为1for i := 0; i < len(dp); i++ {dp[i] = 1}res := 1//3.确定递推公式：dp[i]=max(dp[j]+1,dp[i]);arr[i]>arr[j]. 其中，arr[j]为当前元素arr[i]左侧的所有元素for i := 1; i < len(arr); i++ {//查找上升序列for j := 0; j < i; j++ {//数组序列上升则更新dpif arr[i] > arr[j] {dp[i] = max(dp[j]+1, dp[i]) //i需要与多个j进行比较，因此需获取其中最大的dp[i]}}//找到（更新）最大长度res = max(res, dp[i])}//4.输出结果:dp数组中最大的元素return res
}func max(a int, b int) int {if a >= b {return a}return b
}

具体完整代码你可以参考下面视频的详细讲解。