LIS（最长上升子序列）超全解析
一、LIS 是什么？
LIS（Longest Increasing Subsequence）：给定序列 a，找出最长的一段子序列，满足严格单调递增（a[i]<a[j],i<j）。
- 子序列：不要求连续，但顺序不变。
- 常见变种：
- 严格上升：a[i]<a[j]
- 不下降：a[i]≤a[j]
- 严格下降 / 不下降：把符号反过来即可。
二、问题模型（一句话）
输入：a[1..n]输出：最长上升子序列长度（有时也要输出方案）。
三、解法 1：朴素 DP（O(n^2)，入门必会）
1. 定义状态
dp[i]：以 a[i]结尾的 LIS 长度。
2. 转移方程
dp[i]=max{dp[j]+1∣j<i, a[j]<a[i]}初始：dp[i]=1（每个元素自己是长度 1 的 LIS）。
3. 答案
max{dp[1..n]}。
4. 代码（C++）
int lis_dp(const vector<int>& a) { int n = a.size(), ans = 1; vector<int> dp(n, 1); for (int i = 1; i < n; ++i) for (int j = 0; j < i; ++j) if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1), ans = max(ans, dp[i]); return ans; }5. 适用范围
n≤10^3 完全够用；数据再大就会超时。
四、解法 2：贪心 + 二分（O(nlogn)，竞赛最优）
1. 核心思想（极关键）
维护一个数组 f：
- f[k] 表示：长度为 k+1 的上升子序列的 “最小末尾”。
- 目的：让末尾尽可能小，为后面元素留出更大空间，从而得到更长序列。
遍历 a[i]：
- 若 a[i]>f.back()：直接接入，长度 + 1。
- 否则：在 f 中找到第一个≥a[i]的位置，替换为 a[i]（保持序列性质，不影响最长长度）。
最终 f 的长度就是 LIS 长度。
2. 为什么正确？
因为我们维护的是 “所有长度为 k 的上升子序列的最小结尾”，这样未来任何新元素能接上去的概率最大。
3. 代码（C++，严格上升）
int lis_optim(const vector<int>& a) { vector<int> f; for (int x : a) { auto it = lower_bound(f.begin(), f.end(), x); if (it == f.end()) f.push_back(x); else *it = x; } return f.size(); }4. 若求 “不下降”（a[j]≤a[i]）
把lower_bound换成upper_bound：
auto it = upper_bound(f.begin(), f.end(), x);五、LIS 常见变种（导弹拦截 / 套路模板）
1）最长不上升子序列（LNIS）
要求 a[j]≥a[i]
- 维护单调不上升数组 f
- 二分：找第一个小于x 的位置（用
greater）
int lnis(const vector<int>& a) { vector<int> f; for (int x : a) { auto it = upper_bound(f.begin(), f.end(), x, greater<int>()); if (it == f.end()) f.push_back(x); else *it = x; } return f.size(); }2）最长严格下降
同理，维护单调下降数组，用lower_bound配合greater。
六、经典应用题（导弹拦截 P1020）
题目两问：
- 一套系统最多拦截多少：最长不上升子序列
- 最少需要多少套：根据 Dilworth 定理，等于最长严格上升子序列长度
所以代码直接套用上述模板，两问分别求即可。
七、避坑清单（笔试常错）
- 初始化不能为 0：dp [i] 初始 = 1；f 为空。
- 区分严格 / 不下降：
lower_bound/upper_bound别搞反。 - 比较器：降序变种必须用
greater<int>()。 - 答案是全局 max：O (n²) 答案是 max (dp)；O (n log n) 答案是 f.size ()。
八、总结（背这句就够）
- LIS = 最长上升子序列
- 朴素 DP：O(n2)，求以每个结尾的最长
- 贪心 + 二分：O(nlogn)，维护 “长度为 k 的最小末尾”
- 变种只改比较器和二分条件，套路完全一样