企业官网建设流程全解析

最近刷题刷到一道很经典的线性dp题目——最长公共上升子序列（Longest Common Increasing Subsequence，简称LCIS）。这题在算法圈子里地位挺高，因为它把最长上升子序列（LIS）和最长公共子序列（LCS）两个经典模型揉在了一起，现场推状态转移的时候很容易卡壳。尤其是状态划分这一步，看似简单，但对“以谁结尾”“属性是什么”的理解稍微差一点，后面代码就写不顺。

这篇东西我打算按自己做题时的思考路径来写：先从两个母题的思路切入，解释清楚为什么LCIS的状态不能直接套LCS，再带着你做一次完整的集合划分推导，最后给出O(n²)的可直接AC代码和打印路径的扩展。适合刚学完LIS和LCS、想在动态规划上再往上走一步的同学，老手也可以重点看第3节的优化trick和第5节的路径回溯，权当复习一下状态设计的感觉。

1. 问题本质：为什么说它是两个模型的“组合题”

1.1 先理清两个“母题”各自的状态设计

要理解LCIS，先回忆两个基础模型的状态长什么样。

最长上升子序列（LIS），核心状态是f[i]表示“以a[i]结尾的最长上升子序列长度”。转移时枚举i之前的所有位置j，只要a[j] < a[i]，就可以从f[j] + 1转移过来。这个过程有一个贪心加二分优化版本，能做到O(nlogn)，但状态本身的含义是不变的——以某个元素结尾。

最长公共子序列（LCS），核心状态是f[i][j]表示“a的前i个字符和b的前j个字符的最长公共子序列长度”。转移就两个方向：a[i] == b[j]时f[i][j] = f[i-1][j-1] + 1，否则在f[i-1][j]和f[i][j-1]里取max。这个模型的精髓在于“前缀视角”，所有状态都挂在两个序列的前缀上，不关心具体以哪个字符结尾。

LCIS这题，要求的子序列有三个性质：来自公共部分、保持两个序列各自的下标递增、数值严格递增。前两个性质是LCS的范畴，最后一个性质是LIS的范畴。于是问题来了：你应该用“前缀”来定义状态，还是用“结尾元素”来定义状态？

我在第一次做题时，第一反应是照搬LCS的f[i][j]，只在a[i] == b[j]的时候尝试做一些上升判断，结果写出来的转移又臭又长，还容易漏状态。后来看了一些题解才发现，这类“既要公共又要单调”的题，状态设计的关键不是像谁，而是看你最后能不能用一个清晰的“集合划分”讲清楚每个状态怎么来。

1.2 LCIS的难点到底卡在哪里

把三个模型放一起对比，可以看得更清楚：

注意LCIS这行的状态定义，我写的是“a前i个与b前j个中，以b[j]结尾”。这是理解整道题最关键的一句话。

为什么不能是“以a[i]结尾”？因为公共子序列要同时出现在两个序列里，如果你固定的是a[i]结尾，那么在b里找对应元素时还要额外判断相等关系，状态转移会变得非常纠结；而固定b[j]结尾，再配合a的前缀i做扫描，就能在枚举过程中天然处理“相等才更新”这个条件。

所以，状态的定义必须回答三个问题：

• 扫描范围是什么：a取了前i个，b取了前j个
• 结尾元素是谁：以b[j]结尾
• 维护的属性是什么：最长序列长度

这种把“范围 + 结尾”组合在一起定义状态的方式，就是线性dp里常说的“状态划分”。LCIS这道题本质上是在训练你，如何为了让转移清晰，去重新设计状态。

2. 状态定义与状态划分的核心思路

2.1 固定“以b[j]结尾”，再枚举a的前缀

正式定义状态：f[i][j]表示“在a[1..i]和b[1..j]中，所有公共上升子序列里，以b[j]结尾的那一类，长度最大值”。

这里有个容易忽略的小细节：既然是以b[j]结尾，那么这个子序列里一定包含b[j]。又因为它是公共子序列，所以b[j]这个值也一定出现在a[1..i]中的某个位置。也就是说，如果a[i]不等于b[j]，那f[i][j]和f[i-1][j]是等价的，因为你把a[i]纳入不考虑也不会影响“以b[j]结尾”这件事。

于是就有了LCS风格的转移骨架：

• 当a[i] != b[j]时：f[i][j] = f[i-1][j]
• 当a[i] == b[j]时：可以在f[i-1][j]的基础上，再考虑把a[i]（也就是b[j]）接到某个前面已经形成的上升子序列后面，长度加1。

后面这种“接上去”的操作，就需要LIS风格的转移了——往前找一个比当前结尾元素更小的“前驱结尾”。

2.2 集合划分的两种常用方案

把这层逻辑用集合划分的语言说清楚，是所有题解都会做的事，但很多题解直接扔结论，没讲为什么这么划。我当时自己推了一遍，发现两种划分方式其实都能做，只是代码写法差很多。

方案一，按“最后一个来源位置”划分。对于f[i][j]，如果a[i] == b[j]，枚举位置k（1 <= k < j），看有没有b[k] < b[j]的f[i-1][k]，如果有，就可以把b[j]接到b[k]的后面。这样转移是：

f[i][j] = max(f[i-1][j], max_{1<=k<j且b[k]<b[j]} (f[i-1][k] + 1))

这个写法直接、好懂，但代价是三层循环，复杂度O(n³)。

方案二，等价但更优雅：在枚举k的过程中，动态维护一个最大值变量。因为随着i固定，j从左往右扫，你其实可以一边扫一边更新“当前满足b[k] < b[j]的f[i-1][k]最大值”，把对k的枚举从内层循环中“提”出来。这就是经典的O(n²)优化，具体细节放到第3节。

两种方案本质上是同一套集合划分，区别在于方案二把方案一里重复计算的max结果用滚动变量保存下来，避免了每次重新枚举。这就是很多解法里说的“前缀最大值优化”，名字听起来高大上，实际就是省了一次重复循环。

3. 三步走：从朴素O(n³)优化到O(n²)

3.1 先写朴素版本，确保逻辑正确

我一般做题的习惯是，先写一版能保证正确的朴素代码，再考虑优化。这样即使后来优化错了，手里也还有一版对照。

这个朴素版本直接把状态定义和集合划分翻译成代码：

#include <iostream> using namespace std; const int N = 3005; int a[N], b[N]; int f[N][N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { f[i][j] = f[i - 1][j]; if (a[i] == b[j]) { int maxv = 0; for (int k = 1; k < j; k++) { if (b[k] < b[j]) maxv = max(maxv, f[i - 1][k]); } f[i][j] = max(f[i][j], maxv + 1); } } } int ans = 0; for (int j = 1; j <= n; j++) ans = max(ans, f[n][j]); cout << ans << endl; return 0; }

为什么答案要取f[n][j]的最大值？因为公共上升子序列并不要求一定以哪个位置结尾，可能a[n]和b[j]完全不相等，所以必须在所有f[n][j]里取max。这个细节很多人写代码时忘了，结果样例能过，一到大数据就莫名其妙少1。

这套代码的时间复杂度是O(n³)，n在1000左右还能勉强跑，到了3000就直接超时。不过逻辑很清晰，适合拿来做对拍验证。

3.2 优化trick：用滚动变量维护“前缀最大值”

现在做优化。观察朴素版本的内层循环：

for (int k = 1; k < j; k++) { if (b[k] < b[j]) maxv = max(maxv, f[i - 1][k]); }

这个循环做的事情，就是在b[1..j-1]里找出所有值小于b[j]的位置k，取f[i-1][k]的最大值。仔细看，这个最大值是随着j的增大可以递推维护的。

假设我们用变量maxv表示“当外层i固定时，在已经扫过的b[1..j-1]中，所有满足b[k] < b[j]的f[i-1][k]的最大值”。那么每次j从1扫到n的过程中，我们可以提前维护一个“全局当前最优”的值cur：

• 每当处理完一个j后，发现b[j] < b[未来的某值]时，f[i-1][j]就可能成为未来的候选；
• 所以我们在窗口右移的过程中，维护“当前已经扫过的所有位置里，值小于当前b[j]的f最大值”。

更具体的写法是：在遍历j之前初始化cur = 0，当a[i] > b[j]时更新cur = max(cur, f[i-1][j])。你要注意，这里比较的是a[i] > b[j]而不是b[k] < b[j]，为什么？

因为我们在内层循环里判断的是b[k] < b[j]，而外层循环固定了a[i]，只有当a[i] == b[j]时才会真正用到cur。为了让cur代表“所有值小于a[i]的b[k]对应的f最大值”，我们在扫描j时，只要发现b[j] < a[i]，就说明b[j]可以作为未来以a[i]结尾的序列的前驱候选，于是用f[i-1][j]更新cur。

这样一来，等到a[i] == b[j]的时候，cur已经自动维护好了，直接取cur + 1就行。

3.3 最终一维滚动数组实现

状态转移时，f[i][j]只依赖f[i-1][j]和f[i-1][k]，都是上一轮i-1的结果，所以可以去掉第一维，只保留一维数组f[j]。但这有个小陷阱：如果直接原地更新，f[j]可能会被本轮i覆盖，影响后面j的判断。

好在我们的转移逻辑里，用到f[j]的地方有两类：

• a[i] != b[j]时，f[j]保持不变，继承上一轮结果；
• a[i] == b[j]时，f[j] = max(f[j], cur + 1)，其中cur是在本轮已经更新过的变量，只依赖上一轮的f[k]，不依赖本轮被覆盖后的f[k]。

于是滚动数组是安全的。完整代码如下：

#include <iostream> #include <algorithm> using namespace std; const int N = 3005; int a[N], b[N]; int f[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; for (int i = 1; i <= n; i++) { int cur = 0; for (int j = 1; j <= n; j++) { if (a[i] == b[j]) { f[j] = max(f[j], cur + 1); } if (b[j] < a[i]) { cur = max(cur, f[j]); } } } int ans = 0; for (int j = 1; j <= n; j++) ans = max(ans, f[j]); cout << ans << endl; return 0; }

这里有几处顺序非常讲究：

1. 进入内层循环时，cur必须为0，代表“还没有找到任何可以作为前驱的元素”。之后每遇到一个b[j] < a[i]，就用f[j]更新cur，表示“这个位置可以作为未来某个以a[i]结尾的子序列的前驱”。

2. 先判断a[i] == b[j]并更新f[j]，再判断b[j] < a[i]并更新cur。如果把顺序反了，当a[i] == b[j]时，b[j] < a[i]为假，不会影响cur，但有一种情况要注意：如果a[i] > b[j]且b[j]本身又和某个a[i]相等，f[j]在同一轮里被更新后，cur用更新后的f[j]继续往后传，这其实是有问题的。因为f[i][j]本来应该用上一轮的f[i-1][j]来更新cur，而不是本轮f[i][j]。好在我们的更新顺序是先处理相等情况，再处理b[j] < a[i]，所以当b[j] < a[i]时，如果a[i] == b[j]为假，f[j]没有被本轮修改，依然是上一轮的值，安全。如果相等为真，那么b[j] < a[i]为假，不会进入更新cur分支，也不会出错。这块逻辑虽然容易绕晕，但理解之后，就会觉得这个顺序设计得非常精妙。

3. 循环结束后，f数组中每个位置的含义是“以b[j]结尾的当前最长公共上升子序列长度”，注意这里并不区分a的前缀到哪里，因为滚动数组已经把i的维度压缩掉了，最终读到的就是处理完整个a数组后的结果。

我测试过这版代码，在n=3000的数量级下运行时间大概是十几毫秒，放竞赛里也完全没有压力。对比朴素版本的秒级超时，这个优化立竿见影。

4. 代码细节与边界处理

4.1 初始化为什么全部为0，而不是负无穷

有些dp问题要求初始化为负无穷，比如求恰好装满的背包问题。这里不需要，因为空的公共上升子序列是合法方案，长度为0，它对应着“什么都还没选”的状态。

f数组初始全0，其实就表示：“在a的前0个元素和b的前j个元素中，以b[j]结尾的LCIS长度为0”——虽然b[j]根本不在a里，但长度为0的空序列总存在，不影响正确性。等后续i递增时，f[j]会被逐步更新成真正的长度。

这也是一个通用的判断标准：如果状态允许“空方案”，且题目求的是最大值，初始化为0通常没问题。只有要求恰好某种条件时才考虑负无穷。

4.2 为什么答案要取max，而不是f[n]

很多新手看到f[i][j]定义里的“以b[j]结尾”，就觉得最后答案应该是f[n][n]。但f[n][n]表示的是“以b[n]结尾的最长公共上升子序列”，LCIS不一定非要以b的最后一个元素结尾。比如a和b分别是{1, 3, 2}和{1, 2}，最长公共上升子序列是{1, 2}，长度为2，但它不以b[3]结尾，因为b[3]不存在，序列就截止在b[2]了。所以必须对所有j取max。

4.3 关于“上升”是严格还是非严格

题目一般说“上升”，默认是严格递增，也就是b[k] < b[j]，代码里对应b[j] < a[i]。如果题目改成“非严格上升”，只要把<换成<=即可，但要注意这样可能会引入连续相同元素的序列，需要重新验证状态转移的边界。

还有一个小点：如果a和b里有重复元素，严格上升条件下，同一个值不可能被选两次。比如a是{2, 2}，b是{2}，LCIS长度是1而不是2。如果你的代码写的是<=，就会错误地得到2。这个我在对拍时就踩过坑，所以默认情况下一定用严格小于。

4.4 关于数组长度和数据范围

题目里n的上限常见值是3000，此时二维数组f[3005][3005]是约900万个int，内存约36MB，勉强能过。如果n到5000甚至更大，就必须用滚动数组。所以上面给出的最终代码直接用一维，内存只占约12KB，毫无压力。

另外，输入数据如果从0开始存，代码里循环下标要从0而不是1开始，对应的转移逻辑也要整体往左移一位。我个人习惯从1开始存，这样f[j]和b[j]的下标一一对应，不容易把下标搞混。这属于个人风格，但建议初学者统一用一种，别在刷题时换来换去。

5. 进阶：打印出完整的最长公共上升子序列

竞赛里很多时候只需要输出长度，但面试或实际场景中，考官可能会追问“能不能把序列本身打出来”。这就需要额外记录转移路径。

原理和LCS打印路径类似：开一个pre[j]数组，记录“以b[j]结尾的LCIS，它的前一个元素在b中的位置”。当a[i] == b[j]且cur + 1 > f[j]时，说明当前以b[j]结尾的新长度来自某个位置p，这个p就是维护cur时记录下来的最优前驱位置。

实现时，需要在维护cur的同时，也记录cur对应的下标：

#include <iostream> #include <algorithm> #include <vector> using namespace std; const int N = 3005; int a[N], b[N]; int f[N], pre[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; for (int i = 1; i <= n; i++) { int cur = 0, curPos = 0; for (int j = 1; j <= n; j++) { if (a[i] == b[j]) { if (cur + 1 > f[j]) { f[j] = cur + 1; pre[j] = curPos; } } if (b[j] < a[i]) { if (f[j] > cur) { cur = f[j]; curPos = j; } } } } int ans = 0, endPos = 0; for (int j = 1; j <= n; j++) { if (f[j] > ans) { ans = f[j]; endPos = j; } } vector<int> path; while (endPos) { path.push_back(b[endPos]); endPos = pre[endPos]; } reverse(path.begin(), path.end()); cout << ans << endl; for (int x : path) cout << x << ' '; cout << endl; return 0; }

这段代码里要注意的点：curPos必须和cur同步更新，不能只更新值不更新下标。另外pre数组在执行过程中会被覆盖，但由于我们只需要最终路径，而不是每一轮的完整路径，所以数组覆盖不影响最终结果。这个逻辑和LIS里记录g[i]来回溯的思路一脉相承。

如果题目有多组测试数据，记得在每组数据前把f和pre清零，否则上一次的残留值会导致状态错误。我写代码时曾经因为忘了清pre，导致路径里出现一堆诡异的下标，排查了半天才发现是初始化问题。

6. 常见问题与避坑技巧

做题多了之后，我把LCIS相关的坑整理成一张表，每次写代码前都会快速过一遍：

除了表格里的坑，再分享几个实际的调试心得：

第一，遇到答案不对的情况，先用小规模数据手动对拍。把n设为5以内，分别打印朴素版和优化版的f数组，比对差异。很多时候误差出现在某一轮cur的更新顺序上，肉眼对比数组就能定位。

第二，可以用随机数据生成器写一个暴力O(n³)版，配合O(n²)版做对拍。暴力版代码简单、逻辑直观，是最可靠的“标准答案”。生成随机数组时，注意数值范围不能太小，否则重复元素太多，上升判断容易出歧义。

第三，关于时间复杂度的选择，n在1000以内时，O(n³)大概几千万次运算，也就几十毫秒，直接交了不会有问题；n到了3000以上，O(n³)是27亿次运算，必超时。所以优化版是必会的，不能只会朴素写法。

第四，有一个思维方式上的坑值得强调。很多人包括我最初在内，都试图给LCIS套LIS的“贪心 + 二分”优化。这里要提醒一下：LCIS的公共性导致你不能简单地对b维护一个单调栈，因为每一个上升子序列还必须保证公共约束，贪心策略很难同时满足两个维度。所以常规解法就是O(n²)，不要浪费时间想什么“nlogn解法”。少数论文里有优化到近似O(nlogn)的做法，但实现复杂且适用性有限，竞赛里O(n²)完全够用。

7. 从LCIS到更多线性dp模型的迁移

学完LCIS后，你可以再回头看看LIS和LCS，体会一下“状态定义”这个敲门砖到底有多重要。很多题看起来复杂，其实都是这两个模型的变形组合：

• 最长公共子序列 + 计数：多维护一个数组记录方案数；
• 最长上升子序列 + 字典序最小：贪心选择最早可行位置；
• 最长公共上升子序列 + 路径记录：本节已经做了，本质就是在转移时记录前驱；
• 两个序列的LCIS扩展到k个序列：多维版本，状态设计思路一致，只是维度增加。

这类“模型拼接”题，在面试和算法竞赛里都很常见。套路就是：先把两个母题的状态定义吃透，再针对新题目加一个限制条件，看看状态里需要增加什么维度、转移时需要增加什么判断。LCIS刚好是最好的练手材料，因为它同时涉及“前缀”和“结尾元素”两种视角，逼着你把集合划分想清楚。

我个人刷题时的体会是，LCIS这道题不要背代码，要能在一张白纸上从状态定义开始推出来。推一遍比看十遍题解都管用。每推一次，你对“为什么固定b[j]而不是a[i]”“为什么cur要在内层循环里维护”这些细节的理解就会深一截。等你哪天闭着眼睛都能画出转移图了，再遇到“最长xx子序列”的变种题，思路就会非常顺畅。

最后再分享一个小技巧：如果面试官让你写LCIS，可以先说出状态定义和集合划分逻辑，再写代码。因为大部分面试官更在意你的思考过程，而不是代码默写能力。代码写完之后，主动补一句“这里用滚动数组优化了空间复杂度，原来的二维f简化为一维”，这个细节特别加分，能直接体现你对dp优化的熟练度。