经典算法模型：最长上升子序列 (LIS) 详解
最长上升子序列 (Longest Increasing Subsequence, 简称 LIS) 是动态规划中最基础、也是极其重要的一个模型。 问题描述：给定一个长度为 n 的数组，找出一个最长的单调严格递增的子序列。子序列不需要在原数组中连续。
例如：数组 [10, 9, 2, 5, 3, 7, 101, 18] 的 LIS 是 [2, 3, 7, 101]（或 [2, 5, 7, 101] 等），长度为 4。
解法一：基础动态规划 —— O(n^2)
这是最直观的解法，适合数据范围 n \leq 10^3 的情况。
1. 状态定义
设 dp[i] 表示：必须以第 i 个数字结尾的最长上升子序列的长度。
2. 状态转移方程
对于每个数字 nums[i]，我们往回看它前面的所有数字 nums[j]（j < i）：
- 如果发现
nums[i] > nums[j]，说明nums[i]可以接在nums[j]后面形成一个更长的上升子序列。 - 转移方程：
3. 代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int lengthOfLIS_N2(vector<int>& nums) {
if (nums.empty()) return 0;
int n = nums.size();
vector<int> dp(n, 1); // 每个数字本身可以构成长度为 1 的序列
int max_len = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
max_len = max(max_len, dp[i]);
}
return max_len;
}
解法二：贪心 + 二分查找 —— O(n \log n)
当数据范围 n \leq 10^5 时，O(n^2) 的算法会超时。我们需要利用贪心思想和二分查找进行降维打击。
1. 核心思想：让序列增长得尽可能“慢”
假设我们目前有两个长度同为 3 的上升子序列：[1, 2, 5] 和 [1, 2, 3]。 如果接下来来了一个数字 4，它能接在 3 后面，但接不到 5 后面。 结论：长度相同的上升子序列，结尾元素越小越好，因为这样越容易在后面接上新的数字。
2. 状态定义与维护 (扑克牌接龙法)
维护一个数组 tails，其中 tails[i] 存储的是长度为 i+1 的所有上升子序列中，结尾最小的那个元素。( 神奇的性质：tails 数组必定是严格递增的！)
遍历原数组 nums 中的每个元素 x：
- 如果
x比tails中的所有元素都大，直接把它加到tails末尾。（LIS 长度增加） - 否则，在
tails中用二分查找找到第一个大于等于x的元素，并把它替换为x。 (这一步的意义是：找到了一个长度相同的子序列，用更小的结尾元素x去替换原来的结尾，使得未来更有潜力)
最终，tails 数组的长度就是 LIS 的长度！（注意：tails 数组里的元素不一定是真正的 LIS 序列）
3. 代码实现 (借助 STL lower_bound)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int lengthOfLIS_NlogN(vector<int>& nums) {
vector<int> tails; // tails[i] 存长度为 i+1 的 LIS 的最小结尾
for (int x : nums) {
// lower_bound 找到第一个 >= x 的迭代器
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) {
// x 比前面所有的结尾都大，LIS 变长了
tails.push_back(x);
} else {
// 贪心：替换掉第一个 >= x 的数，让该长度的结尾变小
*it = x;
}
}
// tails 的长度即为 LIS 的最长长度
return tails.size();
}
拓展：如果题目要求的是“最长不下降子序列 (允许元素相等)”，只需要把 lower_bound 换成 upper_bound 即可！
终极实战：如何输出字典序最小的 LIS 具体路径？
在很多高级题目中，不仅要求长度，还要求打印出那个序列。如果在 O(n \log n) 的做法中直接打印 tails，其实是错的，因为替换操作可能破坏了时间前后的相对顺序。
正确解法：在二分替换的过程中，使用辅助数组记录每个元素在 LIS 中的父节点（前驱），最后倒推还原。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 返回具体的 LIS 序列
vector<int> getLISPath(const vector<int>& nums) {
if (nums.empty()) return {};
int n = nums.size();
// pos[i] 记录 tails[i] 在原数组 nums 中的下标
vector<int> pos;
// parent[i] 记录原数组第 i 个元素接在哪个元素（下标）的后面
vector<int> parent(n, -1);
for (int i = 0; i < n; ++i) {
// 自定义二分查找，找第一个 >= nums[i] 的位置
int left = 0, right = pos.size() - 1;
int target_idx = pos.size();
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[pos[mid]] >= nums[i]) {
target_idx = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
// 记录父节点：当前元素接在它前一个位置元素的后面
if (target_idx > 0) {
parent[i] = pos[target_idx - 1];
}
// 维护 pos 数组 (相当于维护 tails)
if (target_idx == pos.size()) {
pos.push_back(i);
} else {
pos[target_idx] = i;
}
}
// 倒推还原路径
vector<int> lis;
int curr = pos.back(); // LIS 的最后一个元素的真实下标
while (curr != -1) {
lis.push_back(nums[curr]);
curr = parent[curr];
}
reverse(lis.begin(), lis.end()); // 因为是倒推的，所以要反转
return lis;
}