给你一个整数数组
nums ，找到其中 最长严格递增 子序列 (LIS) 的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，
[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列示例 1：
示例 2：
示例 3：
题目中有两个关键词：
- 子序列不要求连续，所以
[10, 9, 2, 5, 3, 7, 101, 18]里面，[2, 3, 7, 18]是合法子序列，虽然这些元素在原数组中并不相邻。
- 严格递增，所以后一个被选中的数字必须大于前一个数字。比如
[2, 3, 7]合法，但[5, 3, 7]不合法。
这道题的核心难点不在于判断一个序列是否递增，而在于：我们每走到一个数字，都要决定它能不能接在之前某个递增子序列后面。
- 如果能接，它会让那个子序列长度加一；
- 如果不能接，它可能只能自己单独成为一个长度为
1的序列。
解法一：递归 （暴力解法）
最直接的想法是从左到右扫描数组。对每个位置，我们问一个很朴素的问题：当前这个数字要不要加入当前的递增子序列？
- 如果当前数字比上一个选中的数字大，那么它有资格被选中。于是我们有两个选择：选它，或者不选它。
- 如果当前数字不够大，那它就不能选，只能跳过。
这个思路的 intuition 很自然：LIS 本质上就是在数组里挑一些数字，而且挑出来的数字要保持原来的相对顺序，并且越来越大。
所以递归可以用两个变量来描述状态：
prev表示上一个被选中的元素下标，
cur表示当前正在考虑的元素下标。
当
nums[cur] > nums[prev] 时，当前元素可以接到后面；否则只能跳过。递归会枚举所有可能的子序列，所以一定能找到最优答案。
不过它的问题也很明显：同一个子问题会被反复计算。
例如，前面选择路径不同，但最终可能都会走到同一个
(prev, cur) 状态。
复杂度分析
- 时间复杂度是
O(2^n)。每个元素大致都有选或不选两种分支，递归树规模指数级增长。
所以这个版本更适合用来理解问题结构，而不是作为最终提交方案。
- 空间复杂度是
O(n)，主要来自递归调用栈深度。
解法二：记忆化搜索 (选或不选 - 二维状态 DP)
普通递归慢是因为重复做了太多相同的计算。对于同一个
(prev, cur)，无论我们是通过哪条路径走到这里，后面能得到的最长长度都是一样的。所以，递归状态只由 prev 和 cur 决定，和之前怎么走到这里无关。我们可以把每个
(prev, cur) 的结果缓存起来。下次再遇到相同状态时，直接返回结果，不再展开递归树。思路仍然是“选或不选”，从原问题出发，不断拆成子问题。
解法示例：
nums = [10, 9, 2, 5]初始状态：
dfs(-1, 0) 表示“还没选任何数，现在看 10”。这时有两种选择：
- 不选 10 →
dfs(-1, 1) - 表示 仍然还没选任何数，现在看
9。因为prev == -1，所以9可以作为第一个数被选。
- 选 10 →
1 + dfs(0, 1) dfs(0, 1)表示 上一个选的是nums[0] = 10，现在看nums[1] = 9- 因为
9 > 10不成立，所以9不能选，只能跳过
复杂度分析
- 时间复杂度是
O(n^2)
状态由
(prev, cur) 决定。prev 有 n + 1 种可能，cur 有 n 种可能，所以状态数是 O(n^2)。每个状态只做 O(1) 的决策。- 空间复杂度是
O(n^2)
用于缓存所有状态；递归栈额外占用
O(n)。解法三：记忆化搜索 (枚举前一个数 - 一维状态 DP)
我们不是简单地关心每个元素选不选，而是关心被选中的相邻两个元素之间是否满足递增关系。因此，“枚举最后一个数的前一个数是谁”比“选或不选”更贴合问题结构。
LIS 的一个更自然的状态其实是“以某个元素结尾”的最长递增子序列长度。
定义：
dfs(i) = 以 nums[i] 结尾的最长递增子序列长度 , 表示 nums[i] 必须被选中，并且必须是这个子序列的最后一个元素。如果我们想计算
dfs(i) ，就需要看它前面的所有位置 j < i。只要 nums[j] < nums[i]，说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面：如果前面没有任何数字能接上来，那么
nums[i] 自己就是一个长度为 1 的递增子序列。复杂度分析
- 时间复杂度是
O(n^2)。一共有n个状态，每个状态最多枚举前面的O(n)个元素。
- 空间复杂度是
O(n)，用于缓存dfs(i)的结果；递归栈最多O(n)。
解法四：动态规划
和解法三类似，
dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。计算 dp[i] 时枚举所有 j < i，只要 nums[j] < nums[i]，就可以把 nums[i] 接在 nums[j] 后面。状态转移函数:
dp[i] = max(dp[i], dp[j] + 1)。最终答案是
max(dp)，而不一定是 dp[-1]。因为最长递增子序列不一定以最后一个元素结尾，所以答案应该是所有 dp[i] 的最大值。解法示例
输入是: nums = [10, 9, 2, 5, 3, 7, 101, 18]
一开始，每个数字都可以自己形成一个长度为
1 的递增子序列，所以：- 当我们看到
5时，它前面比它小的数字有2，所以5可以接在2后面，得到长度2。
- 当我们看到
7时，它前面比它小的数字有2、5、3。 - 其中以
5或3结尾的递增子序列长度已经可以是2，所以7接上去之后，长度变成3。
- 当我们看到
101时，它可以接在7后面，形成长度4的递增子序列 - 比如
[2, 5, 7, 101]或[2, 3, 7, 101]。
- 最后
18也可以接在7后面，形成[2, 3, 7, 18]，长度同样是4。
所以最终答案是
4。复杂度分析
- 时间复杂度是
O(n^2)。外层枚举i，内层枚举所有j < i。
- 空间复杂度是
O(n)，需要一个dp数组保存每个位置作为结尾时的最优长度。
解法五：贪心 + 二分查找 （推荐）
前面的 DP 已经足够直观，但它有一个瓶颈：每次计算
dp[i] 时，都要回头扫描所有 j < i。如果我们想优化，就要问：这些历史状态里，有没有一些信息其实是冗余的？答案是有。
假设我们已经知道两个长度都为
2 的递增子序列：[2, 5] 和 [2, 3]。这两个序列长度一样，但
[2, 3] 明显更有潜力。因为它的结尾更小，后面只要遇到比 3 大的数字就能接上；而 [2, 5] 必须遇到比 5 大的数字才行。换句话来说，对于相同长度的递增子序列，结尾越小越好，因为它越容易接上后面的数字，未来可扩展性越强。所以，我们只需要保留结尾最小的那个。 于是我们维护一个数组
tails 。tails[k] 表示长度为 k + 1 的递增子序列中，最小的结尾值。比如：tails = [2, 3, 7] 表示目前：
- 长度为
1的递增子序列，最小结尾是2；
- 长度为
2的递增子序列，最小结尾是3；
- 长度为
3的递增子序列，最小结尾是7。
当新数字
x 到来时：- 如果
x > tails[-1]，说明它可以接在当前最长序列后面，最长长度增加。
- 否则，我们就在
tails里找到第一个大于等于x的位置，把它替换成x。
这个替换不会让当前 LIS 长度变长，但会让某个长度的递增子序列的结尾变小，从而提高未来扩展的机会。
因为
tails 本身是递增的，所以这个位置可以用二分查找找到。当遍历完所有
x, tails 的长度就是 LIS 的 长度。复杂度分析
- 时间复杂度是
O(n log n)。每个元素处理一次，每次用二分查找定位替换位置。
- 空间复杂度是
O(n)，最坏情况下tails长度等于n，例如数组本身严格递增。
解法六：贪心 + 二分查找的原地优化 （最优解）
如果要进一步追问空间优化，可以把
tails 直接复用到原数组 nums 里。因为我们最终只需要答案长度，不需要保留原数组内容，所以可以用 nums 的前缀区域模拟 tails。这个版本和上一版逻辑完全一样，只是额外维护一个变量
size，表示当前 tails 的有效长度。每次二分查找时，只在 nums[0:size] 这个有效区间里查找。复杂度分析
- 时间复杂度是
O(n log n)。
- 空间复杂度是
O(1)，因为直接复用了输入数组，只使用了常数个额外变量。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-300-最长递增子序列
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 240] 搜索二维矩阵 II
下一篇
Production Agents Need Workflow Graphs