最长上升子序列（Longest Increasing Subsequence, LIS）问题就是就是要求从一个给定的序列中找出一个最长的升序子序列，注意这里的子序列不要求连续，和子串（要求连续）的概念是不一样的。另外一个变体就是最长非降序子序列，和 LIS 的区别就是序列中是否可以有相等的数。
给定序列 nums[] = {2, 7, 1, 5, 6, 4, 3, 8, 9}，求 LIS 的长度，下面给出两种解法
- 定义
dp[i]表示以nums[i]结尾的最长上升子序列长度。初始化可以为dp[i] = 1
int lengthOfLIS(vector<int>& nums) {
if(nums.size() == 0) {
return 0;
}
// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
vector<int> dp(nums.size(), 1);
int max = 1;
// 从以 nums[i] 结尾的序列中找最长的递增子序列
for(int i = 1; i < nums.size(); i ++) {
// 只有当 nums[i] 大于前面数值时才可能统计 dp
for(int j = 0; j <= i-1; j ++) {
if(nums[i] > nums[j]) {
if(dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
}
max = dp[i] > max ? dp[i] : max;
}
return max;
}- 时间复杂度：两个 for 循环，时间复杂度为
$O(n^2)$
这里有一个贪心的思想：对于一个上升子序列而言，显然其结尾的元素越小越好，这样就越有利于后面接上其他元素让子序列更长。
tail[i]表示长度为 i+1 的 所有 上升子序列尾部元素的最小值- tail[0] 表示长度为 1 的所有上升子序列中，结尾元素最小的那一个
- 假设给定
[10, 9, 2, 5, 3, 7, 101, 18]，长度为 2 的所有上升子序列中，结尾元素最小子序列为[2, 3]，因此tail[1] = 3 - tail 不是 LIS，只是用于求解 LIS 问题的状态数组，其下标和LIS长度有一个数值为 1 的偏差
- 根据贪心的思想，tail 序列一定是严格递增的，可以用反证法证明，参考 liweiwei 题解
- 遍历数组 nums 的过程中，维护 tail 数组的定义：和 tail 最后一个元素比较大小
- nums[i] > tail.back()，直接将 nums[i] 放在 tail 后面（注意这里是 严格大于）
- nums[i] <= tail.back()，在 有序 的 tail 中找到第1个 大于等于 nums[i] 的元素，将其用 nums[i] 替换
- 如果存在等于 nums[i] 的元素可以没必要替换，因为以 nums[i] 结尾的上升子序列已经存在了
- 如果存在大于 nums[i] 的元素就要替换，因为这时候找到了一个 结尾更小 的 相同长度 的上升子序列
- 最终有序数组 tail 的长度就是 LIS 的长度
int lengthOfLIS(vector<int> &nums) {
int len = nums.size();
if (len < 2) return len;
// tail表示长度为i+1的所有上升子序列的尾部元素最小值
int tail[len];
tail[0] = nums[0];
int end = 0; // end 表示 tail 最后一个已经赋值的元素的下标
for (int i = 1; i < len; ++ i) {
if (nums[i] > tail[end]) { // 情况1：严格大于
++ end;
tail[end] = nums[i];
} else { // 情况2：小于就需要二分查找
// 可以直接调库函数
// int id = lower_bound(tail, tail+end+1, num[i]) - tail;
// tail[id] = nums[i];
// 在 [0...end] 中找到第一个大于等于 nums[i] 的元素
int left = 0, right = end;
while (left < right) {
int mid = (right - left) / 2 + left;
if (tail[mid] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}
// 这里为了不加入额外的判断，等于的情况也直接替换了
tail[right] = nums[i];
}
}
return end + 1;
}- 时间复杂度：遍历数组 O(n)，二分查找 O(logn)，总的时间复杂度为
$O(n\log n)$
如果是找最长非递减子序列呢？
- 二分查找就需要在 tail 中找到第一个 大于 nums[i] 的元素
- 例如考虑
[7,7,7,7,7,7,7]，每次就必须在 tail 中找到 大于 7 的元素，也就是直接加在 tail 后面，最终 tail 和 nums 一样 - 核心思路就是 「让序列上升得尽可能慢」。不降子序列可以理解为允许 tail 数组中有相同元素，在允许有相同元素的情况下，为了让序列上升得尽可能慢，nums[i] 应当排在和他相同的元素后面，也就是 tail 中的大于 arr[i] 的第一个位置
🔥🔥🔥 小技巧
- 求 最长严格递增子序列 需要二分找到 大于或等于 当前元素的元素位置（即 C++ 中的
lower_bound） - 求 最长不降子序列 需要二分找到 大于 当前元素的元素位置（即 C++ 中的
upper_bound）
| 题目 | 说明 | 题解 |
|---|---|---|
| 300. 最长递增子序列 | 常规的 LIS，按照上面代码直接秒杀 | 通过 |
| 2111. 使数组 K 递增的最少操作次数 | 分成 k 组，每组中找到最长非递减子序列（LnDS），最小修改次数=每组长度 - LnDS长度 | 0x3F |
| 使数组 K 严格递增的最少操作次数 | 分成 k 组，还是和2111一样求 LnDS，但是需要将每个分组减去下标之后求 LnDS | 0x3F |
| 1143. 最长公共子序列 | 求 s1 s2 最长公共子序列，很常规的二DP | 负雪明烛 |
2111 扩展：使数组 K 严格递增的最少操作次数
把每个数减去其下标，然后对所有正整数求最长非降子序列。
举个例子，现在每 k 个数选一个数，假设选出来的数组是 arr = [3,2,4,5,5,6,6]。
解释：严格递增说明对应任意的 i > j，有 arr[i] - arr[j] >= i - j，变形得到 arr[i] - i > arr[j] - j，所以构造 b[i] = arr[i] - i，求 b 的最长非递减子序列就可以，每个数减去其下标后就是 [3,1,2,2,1,1,0]。
对这个数组中的正整数求最长非降子序列，那就是 [1,1,1] 了，对应原始数组的 [*,2,*,*,5,6,*]，这三个数字保留，其余数字修改完成后就是 [1,2,3,4,5,6,7]，符合严格递增且均为正整数的要求。
注：上述减去下标的技巧，主要是为了能让保留的数字 之间 可以 容纳 严格递增的数字。否则，若直接按照最长严格递增子序列的求法，会得到例如
[*,2,4,5,*,6,*]这样的错误结果。