最长上升子序列，英文名 Longest Increasing Subsequence，简称 LIS，在面试中属于难度较大，但又非常高频的题目。
LIS 题目大致有以下这些，欢迎补充哦：
- 300. 最长递增子序列（基础）
- 334. 递增的三元子序列（简单）
- 354. 俄罗斯套娃信封问题（二维，排序）
- 673. 最长递增子序列的个数（动态规划）
- 960. 删列造序 III（动态规划）
- 1691. 堆叠长方体的最大高度（三维，排序）
- 1713. 得到子序列的最少操作次数（进阶）
开始阅读本文之前，强烈建议先把最基础的这道题做了，做完再继续看
总体思路
如果你不知道最长上升子序列是什么意思，也没有做那道题，我——当然不会怪你 😊
最长上升（递增）子序列这道题是最最基本的，也是最常考的题了，其他题目都是由它衍生而来。题意也好理解，比如 [1, 4, 3, 5, 6, 7, 4, 4, 6] 中最长的递增子序列就是 [1, 4, 3, 5, 6, 7, 4, 4, 6] 或者 [1, 4, 3, 5, 6, 7, 4, 4, 6]，由于我们只需输出最长的长度，所以最终答案为 5。
注意，子序列不一定是连续的，子串才必须是连续的。
重点来了：
- 最长上升子序列问题一般就两种解法：
- 多维问题一般
解释一下，对于第一点，遇到这类问题一般优先考虑二分，二分解决不了的话考虑动态规划；
对于第二点中的多维问题就是将输入中的每个元素换成二维数组或三维数组，比如：
- 354. 俄罗斯套娃信封问题，
envelopes = [[5,4],[6,4],[6,7],[2,3]] - 1691. 堆叠长方体的最大高度，
cuboids = [[50,45,20],[95,37,53],[45,23,12]]
对于这种多维问题，一般先考虑排个序，然后再用 LIS 的处理方法。
300. 最长递增子序列
官方题解中描述的方法为动态规划和贪心+二分，按照前面的思路我们先想二分。
思路
贪心：要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。也就是我们维护一个 d = []，每次插入时使用二分来寻找合适的位置。由于 Python 中有相关的库 bisect，所以这道题的代码可以写成这样：
代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
d = []
for n in nums:
idx = bisect.bisect_left(d, n) # idx 为假如 n 插入到 d 中的索引
if idx == len(d): d.append(-1)
d[idx] = n
return len(d)以上就是 LIS 问题基本形式的解法，Python 直接用库，不能调库的使用官方题解方法二的二分模板。是不是好像也不太难？
334. 递增的三元子序列
思路
仔细读完题一想，这道题的意思不就是判断一下最长子序列的长度是否大于等于三吗？
所以在上一道题的最后一行代码后加 >= 3
代码
... >= 3
354. 俄罗斯套娃信封问题
思路
题目中说，当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
也就是说，对于第 i 个信封envelopes[i]，我们不仅要保证 envelopes[i][0] > envelopes[i - 1][0]，也要保证 envelopes[i][1] > envelopes[i - 1][1]，这时第 i - 1 个信封可以装在第 i 个信封里。
如何权衡这两点呢？这里用到了一个技巧，将信封先按长度升序排列，再按宽度降序排列。
排序之后不考虑长度，只寻找宽度序列中的 LIS 即可。
代码
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
def LIS(A):
d = []
for n in A:
index = bisect.bisect_left(d, n)
if index == len(d): d.append(0)
d[index] = n
return len(d)
envelopes.sort(key=lambda x: (x[0], -x[1]))
return LIS([e[1] for e in envelopes]) 673. 最长递增子序列的个数
思路
这道题就有点不讲武德了，我们容易得到最长子序列的长度，但是问该长度下有多少个子序列，显然已经超出了二分的能力范围，这时候就需要考虑动态规划了。
这类问题的动态规划一般这样考虑：
篇幅原因请直接移步 官方题解，我想表达的只有这句话，希望对你有用。
代码
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
length = [0] * n
counts = [1] * n
for j in range(n):
for i in range(j):
if nums[i] < nums[j]:
if length[i] >= length[j]:
counts[j] = counts[i]
length[j] = length[i] + 1
elif length[i] + 1 == length[j]:
counts[j] += counts[i]
longest = max(length)
return sum(c for i, c in enumerate(counts) if length[i] == longest)960. 删列造序 III
思路
本题的难点在于我们需要从题目中抽取出 LIS 模型，之前我们看到的题目变种中有将数组中的每个元素变为二维或三维数组，当时我们使用了排序的技巧。
现在每个元素变成了字符串，且字符串长度可能会很长。
这里的技巧在于需要将 每一列的所有字符 看成一个元素，求这些列的 LIS。其中，每一行都要满足字典序。如下图：
代码
class Solution:
def minDeletionSize(self, A: List[str]) -> int:
n = len(A[0])
dp = [1] * n
for j in range(n):
for i in range(j):
if all(A[r][i] <= A[r][j] for r in range(len(A))):
dp[j] = max(dp[j], dp[i] + 1)
return n - max(dp)1691. 堆叠长方体的最大高度
思路
这道题是有点困难的，难点在于知道排序却不知道如何排。与 354 套娃问题类似，由于长方体可以任意旋转，我们可以选择长宽高中较小的两个边作为套娃问题的长和宽，这样剩下的高度就会尽可能的高了。
因此我们仍然先对长宽高排序，再将每个长方体按照最短边升序排列，利用动态规划求解。
代码
class Solution:
def maxHeight(self, cuboids: List[List[int]]) -> int:
n = len(cuboids)
for c in cuboids:
c.sort()
cuboids.sort()
dp = [0] * n
ans = 0
for i in range(n):
for j in range(i):
if cuboids[j][1] <= cuboids[i][1] and cuboids[j][2] <= cuboids[i][2]:
dp[i] = max(dp[i], dp[j])
dp[i] += cuboids[i][2]
ans = max(ans, dp[i])
return ans1713. 得到子序列的最少操作次数
思路
这道题同样需要一点技巧，仔细思考发现，这道题目的意思是在 arr 中找到 target 中的一个 LIS，比如：
- target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
- arr 中能够找到 target 的 LIS = [4,8,1]
- 所以需要补充的字符数是
len(target) - len(LIS) = 3
而 [4,8,1] 本身并不是升序的，而所在下标是升序的，所以我们需要使用哈希表来映射一下。
代码
class Solution:
def minOperations(self, target: List[int], arr: List[int]) -> int:
res = 0
dic = {value : index for index, value in enumerate(target)}
d = []
for n in arr:
if n not in dic:
continue
index = bisect.bisect_left(d, dic[n])
if index == len(d): d.append(-1)
d[index] = dic[n]
return len(target) - len(d)总结
能够看到这里已经非常感谢了，如果有什么问题，欢迎在下方留言，我们一起讨论 😊
我们看到 LIS 问题其实本身不难，解法也相对固定，难就难在实际题目中，是否能够感觉出来这是一道 LIS 的题目，并准确无误地实现它。
