300. 最长上升子序列

---

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/longest-increasing-subsequence

题目

---

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

示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

你算法的时间复杂度应该为 $O(n^2)$ 。

进阶: 你能将算法的时间复杂度降低到 $O(n\log n)$ 吗?

解题思路

---

思路：动态规划、二分查找

在这里，题目要求找到给定无序数组中最长上升子序列的长度。

看示例部分，我们可以发现，这里要求返回的序列并非要求要连续的。

动态规划

这里我们用动态规划的方法来解决这问题。

状态定义

设 dp[i] 为以 nums[i] 结尾的上升子序列的长度。

状态转移方程

在这里，我们要求 dp[i] 之前，需要先求得 dp[0...i-1] 的值。

然后只要 nums[i]的值严格大于 i 前面的某个数，那么 num[i] 便可以跟在这个数后面，形成更长的子序列。

也就是说 dp[i] 就等于 i 前面严格小于 num[i] 中 dp 值最大 + 1。

那么状态方程如下： $$dp[i]=max(dp[j])+1$$ 其中 $0\le j<i$，并且 $num[i]>num[j]$。

状态初始化

因为单独一个数字也能算作是一个长度为 1 的上升序列，那么先将 dp 数组初始化为 1。

注意：

这里不能直接返回 dp 数组的最后一个状态值，这里要求返回最长的上升子序列，那么最终要返回 dp 数组中的最大值。

具体的代码实现如下：

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: if not nums: return 0 n = len(nums) dp = [1] * n for i in range(n): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1) # 返回 dp 数组最大值 return max(dp)

复杂度分析：

时间复杂度：$O(N^2)$，$N$ 为数组 nums 的长度。两层遍历都为线性时间 $O(N)$。空间复杂度：$O(N)$，额外使用长度为 $N$ 的 dp 数组。

动态规划+二分查找

进阶部分，希望时间复杂度能够降到 $O(N\log N)$。下面就前面的方法进行优化。

我们可以观察示例中的上升子序列，如果需要获得更长的子序列，那么子序列上升的幅度越小越好。

也就是，当上升子序列中最后的元素越小，那么与后面的元素连接形成更长的子序列的可能性更大。

状态定义

这里要重新定义状态。设 tail[i] 表示长度为 i+1 子序列尾部元素值。

状态转移方程

在这里 tail 列表一定是要严格递增的。这里用反证法来证明：

证明： 当 $i<j$ 时，都有 $tail[i]<tail[j]$。

反证法：

假设 $i<j$ 时，存在 $tail[i]>=tail[j]$。

这里 $tail[i]$ 表示长度为 $i+1$ 子序列尾部元素值，$tail[j]$ 同理。

也就是说，上面的假设中，较短子序列中的尾部元素值 要大于 较长子序列中的尾部元素值 。

现在，将 较长子序列 从尾部开始删减元素，直至长度等于 较短子序列 的长度（$i+1$）。假设在这个缩减后长度为 $i+1$ 的序列尾部元素值为 $tail[k]$，那么此时 $tail[k]<tail[j]$ ，也就是说长度为 $i+1$ 的子序列的尾部元素值更小，那么这就跟原假设 $tail[i]>=tail[j]$ 矛盾。

故，当 $i<j$ 时，都有 $tail[i]<tail[j]$。

转移方程

设 length 为 tail​ 数组的长度。遍历数组 nums，假设当前元素为nums[i]，这里可能出现的情况：

若 nums[i] 大于 tail 数组尾部元素，那么可以将 num[i] 直接放到 tail 数组尾部，更新长度 length，令 length +1。若不存在上面的情况，那么则需要通过二分查找在 tail 数组中找到第一个比 nums[i] 大的元素，用 nums[i] 替换。

状态初始化

初始化 tail 数组值为 0。

令 tail[0]=nums[0]，初始长度 length 为 1。

具体的代码实现如下：

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) # 处理数组为空的情况 if not nums: return n # 一般情况，初始化 tail 数组值都为 0 tail = [0] * n # 令 tail[0] = nums[0]，length 长度为 1 tail[0] = nums[0] length = 1 # 开始遍历 for i in range(1, n): # 如果出现 nums[i] 大于 tail 数组末尾元素 # 将 nums[i] 放到末尾，更新 length if nums[i] > tail[length-1]: tail[length] = nums[i] length+=1 continue # nums[i] 不大于 tail 数组末尾元素时 # 利用二分查找在 tail 数组索引为 [0 , length) 之间的元素找到第一个大于 nums[i] 的元素 # 将其替换为 nums[i] left = 0 right = length-1 while left < right: mid = left + (right-left) // 2 if nums[i] > tail[mid]: left = mid + 1 else: right = mid tail[left] = nums[i] return length

复杂度分析：

时间复杂度：$O(N\log N)$。$N$ 为 nums 数组的长度，遍历 nums 数组需要 $O(N)$。遍历查找元素使用二分查找需要 $O(\log N)$，所以总时间为 $O(N\log N)$。空间复杂度：$O(N)$。tail 数组的开销。

欢迎关注

---

公众号 【书所集录】

---

如有错误，烦请指出，欢迎指点交流。