LIS = 从一串数里挑出「严格越来越高」的一段：可以不连续（可以跳过），但顺序不能乱。二维 DP 是填格子表，LIS 是一排格子表：dp[i] = 以第 i 个数结尾的最长上升子序列长度。
想象全班按身高排队，老师要挑出「严格越来越高」的一队人代表班上去比身高：可以从队伍任何位置挑人、可以跳过不想选的人，但顺序不能乱（不能把站后面的挪到前面），而且必须严格变高（一样高不算）。最长的这一队，就是「最长上升子序列」（LIS，Longest Increasing Subsequence）。「子序列」和「子串」不一样：子串必须连续，子序列只要保序。DP 思路：站在第 i 个人身上问：「以我结尾的最长队伍多长？」——答案 = 在我前面、比我矮的人里，挑一个「以他结尾的队伍」最长的，把他接上（dp[i] = max(dp[j]) + 1，j < i 且 a[j] < a[i]）；前面没人能接，就自己单独成队（dp[i] = 1）。最后答案 = 所有 dp[i] 里的最大值。
a = 3 1 4 1 5 9 2 6 里手挑出一条上升子序列。// a = 3 1 4 1 5 9 2 6（圆周率 π 的前 8 位，经典例题） // 位置: 1 2 3 4 5 6 7 8 // 子序列：保序、可以跳过 挑 3, 4, 5, 9 → 位置 1,3,5,6 → 顺序没乱、严格上升 ✓ 挑 1, 5, 9 → 位置 2,5,6 → 也是子序列 ✓ 挑 9, 3 → 9 在位置 6、3 在位置 1 → 顺序乱了 ✗ // 子串（子段）：必须连续 3 1 4 → 位置 1,2,3 连续 ✓（它同时也是子序列） 3 4 5 → 不连续 ✗（子串不行，但子序列可以） // 手挑一条「严格上升」的子序列： 3 → 4 → 5 → 9 长度 4 1 → 4 → 5 → 6 长度 4（跳过 9，改挑 6） // 问题：还有长度 5 的吗？——子任务 2 用 DP 一锤定音
a[j] < a[i]（严格小于）。写成 <= 就把「1 1」当成上升了——那是「不下降」，不是「上升」。dp[i] = 1 + max{ dp[j] | j<i 且 a[j]<a[i] }（没人能接就 1），手推前 6 个数的 dp 表。// 定义：dp[i] = 「以 a[i] 结尾」的最长严格上升子序列长度 // 转移：站在 i，回头看所有 j < i： // 若 a[j] < a[i]：可以把 a[i] 接在 a[j] 后面 → 候选 dp[j] + 1 // dp[i] = 所有候选的最大值；一个候选都没有 → 1（自己单独成队） // 手推 a = 3 1 4 1 5 9（前 6 个数） i=1 (a=3)：前面没人 dp[1] = 1 i=2 (a=1)：3 不是 < 1 dp[2] = 1 i=3 (a=4)：3<4 → 1+1=2；1<4 → 1+1=2 dp[3] = 2 i=4 (a=1)：3,1,4 都不 < 1 dp[4] = 1 i=5 (a=5)：候选 3(1),1(1),4(2),1(1) → 最大 2 dp[5] = 3 i=6 (a=9)：候选最大 = dp[5] = 3 dp[6] = 4 a: 3 1 4 1 5 9 dp: 1 1 2 1 3 4 ← 一格一格填，每格「回头看」左边所有格子
// 全表（每个 i 回头看所有 j<i：a[j]<a[i] 的候选 dp[j]+1） a: 3 1 4 1 5 9 2 6 dp: 1 1 2 1 3 4 2 4 // 验算 dp[7]（a=2）：前面只有 1 < 2（dp=1）→ dp[7] = 1+1 = 2 // 验算 dp[8]（a=6）：前面 a<6 的：3(1),1(1),4(2),1(1),5(3),2(2) // → 最大 3（a[5]=5）→ dp[8] = 3+1 = 4 答案 = max(dp) = 【4】 → 这个序列里没有长度 5 的上升子序列 // 倒推一条 LIS：pre[i] 记录 dp[i] 是从哪个 j 接过来的 a[6]=9 ← a[5]=5 ← a[3]=4 ← a[1]=3 → LIS = 3 4 5 9（长度 4） 其它合法 LIS：1 4 5 9、3 4 5 6、1 4 5 6（长度 4 的都算）
dp[i] = dp[j]+1 更新 + 记 pre、跟踪全局最大值。// 代码骨架（双层循环，O(n²)）： for (int i = 1; i <= n; i++) { // 外层：逐个算 dp[i] dp[i] = 1; pre[i] = 0; // 默认：自己单独成队 for (int j = 1; j < i; j++) { // 内层：回头看前面所有 if (a[j] < a[i] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; // 接在 a[j] 后面更长 pre[i] = j; // 记录「接了谁」（倒推用） } } if (dp[i] > best) { best = dp[i]; bestPos = i; } } // 时间：两层循环都到 n → O(n²)，n ≤ 5000 毫无压力 // 倒推输出：cur = bestPos 开始，沿 pre 走，收集后反转输出
a[j] < a[i] 改成 a[j] <= a[i]（「不下降」允许一样高）。// 题目：输入 n 和 n 个整数，输出最长严格上升子序列的长度， // 并输出其中一条。 // 示例：输入 8 / 3 1 4 1 5 9 2 6 → 长度 4，输出 3 4 5 9 #include <iostream> using namespace std; int main() { int n; cin >> n; int a[5005], dp[5005] = {0}, pre[5005] = {0}; for (int i = 1; i <= n; i++) cin >> a[i]; int best = 0, bestPos = 1; for (int i = 1; i <= n; i++) { dp[i] = 1; // 自己单独成队 for (int j = 1; j < i; j++) { if (a[j] < a[i] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; // 接在 a[j] 后面 pre[i] = j; // 记录来源 } } if (dp[i] > best) { best = dp[i]; bestPos = i; } } cout << "LIS 长度 = " << best << endl; // 倒推一条 LIS（从 bestPos 沿 pre 往回走，先收集再反转） int path[5005]; int cnt = 0; int cur = bestPos; while (cur != 0) { path[++cnt] = a[cur]; cur = pre[cur]; } for (int i = cnt; i >= 1; i--) cout << path[i] << " "; cout << endl; return 0; } // 运行：输入 8 / 3 1 4 1 5 9 2 6 // 输出：LIS 长度 = 4 // 3 4 5 9 // 注意：输出的是「某一条」LIS——有多条时程序只输出其中一条，都算对。