优化)
1. 从一道题说起：为什么要把LCS转成LIS
第一次遇到"最长公共子序列"和"最长上升子序列"这两个概念被放在一起讨论，是在刷一道经典动态规划题的时候。题目本身不复杂：给定两个序列，求它们的最长公共子序列长度。常规做法是二维DP，时间复杂度O(n²)，空间也是O(n²)。但如果题目加了一个限制条件——两个序列都是1到n的排列（即每个元素只出现一次），那就有更优雅的解法了。
这个更优雅的解法，核心思路就是把LCS问题转化为LIS问题。听起来像是变魔术，但背后的逻辑其实很清晰。我先把这个转化的原理讲透，再带你一步步实现。
先说结论：当两个序列都是排列时，LCS可以转化为LIS，时间复杂度从O(n²)降到O(n log n)。这个优化在n达到10⁵甚至10⁶级别时，是决定程序能否通过的关键。
那为什么这个转化成立？关键在于"排列"这个特殊性质。排列意味着每个元素在序列中只出现一次，这就消除了LCS中"同一个元素可能匹配多次"的歧义。具体来说，假设我们有两个排列A和B，我们可以在A中记录每个元素的位置，然后遍历B，把B中每个元素替换成它在A中的位置，得到一个新的位置序列。这个位置序列的LIS长度，就等于A和B的LCS长度。
这个结论不是凭空来的。你可以这样理解：A和B的公共子序列，在A中对应一个下标递增的序列，在B中也对应一个下标递增的序列。当我们把B中的元素映射为它在A中的位置后，B中一个递增的下标序列就变成了一个递增的位置序列。反过来，位置序列的任何一个上升子序列，都对应A和B的一个公共子序列。所以两者一一对应，长度自然相等。
这个转化的妙处在于，它把一个二维的匹配问题，降维成了一维的上升子序列问题。而LIS有O(n log n)的经典解法，用的是贪心加二分。这样一来，整个问题的复杂度就从O(n²)降到了O(n log n)。
我见过不少人在面试或比赛中遇到这个转化，第一反应是"这怎么可能"，但理解之后就会发现，它其实是排列性质的一个自然推论。下面我会把这个转化的每个细节都拆开讲，包括映射表的构建、LIS的二分实现、边界情况的处理，以及实际写代码时容易踩的坑。
2. 核心原理拆解：LCS与LIS的等价性证明
2.1 先搞清楚LCS和LIS各自在求什么
最长公共子序列（LCS）的问题是：给定两个序列A和B，找出一个最长的序列C，使得C同时是A和B的子序列。注意子序列不要求连续，只要求保持相对顺序。比如A = [1, 3, 5, 2, 4]，B = [3, 1, 2, 5, 4]，它们的LCS是[3, 2, 4]或者[1, 2, 4]，长度都是3。
最长上升子序列（LIS）的问题是：给定一个序列，找出一个最长的子序列，使得子序列中的元素严格递增。比如序列[3, 1, 4, 2, 5]，LIS是[1, 2, 5]或者[3, 4, 5]，长度都是3。
这两个问题表面上没什么关系，一个涉及两个序列，一个只涉及一个序列。但排列的特殊性把它们联系起来了。
2.2 排列性质是转化的关键
排列的定义是：一个包含1到n所有整数且每个整数恰好出现一次的序列。比如[2, 1, 4, 3]是一个排列，[1, 1, 2]不是，[1, 3, 4]也不是（缺少2）。
排列有两个重要性质：第一，每个元素唯一；第二，元素的值域和下标范围一致，都是1到n。这两个性质使得我们可以建立元素值到位置的唯一映射。
假设A和B都是1到n的排列。我们构建一个映射pos，其中pos[x]表示元素x在A中的下标（从1开始计数）。因为A是排列，每个x都有唯一的pos[x]。然后我们遍历B，把B中的每个元素b替换成pos[b]，得到一个位置序列P。这个P的长度是n，每个元素是1到n之间的整数。
关键结论：P的LIS长度等于A和B的LCS长度。
2.3 为什么这个等价关系成立
我来给出一个直观但严谨的证明。
先证LCS长度不超过LIS长度。假设A和B有一个公共子序列C，长度为k。C在A中的下标是递增的，设为i₁ < i₂ < ... < iₖ。C在B中的下标也是递增的，设为j₁ < j₂ < ... < jₖ。对于C中的第t个元素cₜ，它在A中的位置是iₜ，在B中的位置是jₜ。当我们把B映射为P后，P中第jₜ个元素就是pos[cₜ] = iₜ。由于j₁ < j₂ < ... < jₖ，P中对应的位置也是递增的，而对应的值是i₁ < i₂ < ... < iₖ，也是递增的。所以P有一个长度为k的上升子序列。因此LIS长度至少是k，即LIS ≥ LCS。
再证LIS长度不超过LCS长度。假设P有一个长度为k的上升子序列，对应的下标是j₁ < j₂ < ... < jₖ，对应的值是P[j₁] < P[j₂] < ... < P[jₖ]。根据P的定义，P[jₜ] = pos[B[jₜ]]，所以pos[B[j₁]] < pos[B[j₂]] < ... < pos[B[jₖ]]。这意味着B[j₁], B[j₂], ..., B[jₖ]这些元素在A中的位置是递增的，所以它们在A中按顺序出现。同时它们在B中也是按顺序出现的（因为j₁ < j₂ < ... < jₖ）。所以它们构成A和B的一个公共子序列，长度为k。因此LCS ≥ LIS。
两个方向合起来，LCS = LIS。证明完毕。
这个证明的核心在于：排列的唯一性保证了映射是一一对应的，不会出现一个元素对应多个位置的情况。如果序列中有重复元素，这个映射就不唯一了，转化也就不成立了。
2.4 转化后的复杂度分析
原始LCS的DP做法需要O(n²)的时间和空间。转化后，构建映射表需要O(n)，遍历B生成P需要O(n)，求P的LIS用贪心加二分需要O(n log n)。总时间复杂度O(n log n)，空间复杂度O(n)。当n = 10⁵时，O(n²)是10¹⁰次操作，肯定超时；O(n log n)大约是1.7×10⁶次操作，轻松通过。当n = 10⁶时，O(n log n)大约是2×10⁷次操作，也在可接受范围内。
这个复杂度差距就是转化的价值所在。在实际比赛中，看到"两个排列求LCS"这样的描述，基本可以确定出题人想考的就是这个转化。
3. 实操过程：从映射表到LIS的完整实现
3.1 构建位置映射表
第一步是读取两个排列A和B，构建pos数组。假设输入是n，然后一行n个整数是A，再一行n个整数是B。我用Python来演示，因为Python的代码可读性最好，逻辑最清晰。
n = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) pos = [0] * (n + 1) for i, x in enumerate(A): pos[x] = i这里pos[x]表示元素x在A中的下标（从0开始）。用从0开始的下标在后续处理中更方便，因为Python的列表索引从0开始。注意pos数组的大小是n+1，因为元素的值域是1到n。
这一步的时间复杂度是O(n)，空间复杂度是O(n)。看起来很简单，但有一个细节需要注意：如果输入不保证是排列（比如有重复元素或值超出1到n），这个映射就会出错。所以在实际使用中，要么题目明确保证是排列，要么需要先做一次校验。
3.2 生成位置序列P
第二步是遍历B，把每个元素替换成它在A中的位置。
P = [pos[x] for x in B]这一行代码就完成了转化。P的长度是n，每个元素是0到n-1之间的整数。因为A是排列，pos[x]对每个x都有定义，不会出现KeyError或越界。
到这里，问题已经变成了：求P的最长上升子序列长度。注意是严格上升，因为LCS中的元素在A中的位置必须严格递增（每个元素只出现一次，不可能有两个元素在同一个位置）。
3.3 用贪心加二分求LIS
LIS的O(n log n)解法是经典算法，核心思想是维护一个数组tails，其中tails[i]表示长度为i+1的上升子序列的最小末尾元素。遍历P中的每个元素x，用二分查找在tails中找到第一个大于等于x的位置，替换它；如果找不到，就把x追加到tails末尾。最终tails的长度就是LIS长度。
import bisect tails = [] for x in P: idx = bisect.bisect_left(tails, x) if idx == len(tails): tails.append(x) else: tails[idx] = x print(len(tails))这里用bisect_left是因为我们求的是严格上升子序列。如果求的是非严格上升（允许相等），应该用bisect_right。这个区别很关键，用错了会导致结果偏大。
为什么这个贪心策略是正确的？直观理解是：对于每个长度，我们总是希望末尾元素尽可能小，这样后面才有更多机会接上更大的元素。tails数组始终保持递增（因为每次替换都是把更大的元素换成更小的，不会破坏递增性）。二分查找保证了每次操作是O(log n)，总复杂度O(n log n)。
3.4 完整代码与测试
把上面的步骤合起来，完整代码如下：
import bisect def lcs_of_permutations(A, B): n = len(A) pos = [0] * (n + 1) for i, x in enumerate(A): pos[x] = i tails = [] for x in B: idx = bisect.bisect_left(tails, pos[x]) if idx == len(tails): tails.append(pos[x]) else: tails[idx] = pos[x] return len(tails) # 测试 A = [3, 1, 4, 2, 5] B = [1, 3, 2, 5, 4] print(lcs_of_permutations(A, B)) # 输出3手动验证一下：A = [3, 1, 4, 2, 5]，B = [1, 3, 2, 5, 4]。pos[3]=0, pos[1]=1, pos[4]=2, pos[2]=3, pos[5]=4。遍历B得到P = [1, 0, 3, 4, 2]。P的LIS是[1, 3, 4]或[0, 3, 4]，长度3。对应的公共子序列是[1, 2, 5]或[3, 2, 5]，长度确实是3。
再测一个边界情况：A = [1]，B = [1]。pos[1]=0，P=[0]，LIS长度1。正确。
A = [1, 2, 3]，B = [3, 2, 1]。pos[1]=0, pos[2]=1, pos[3]=2。P=[2, 1, 0]，LIS长度1。A和B的LCS确实是1（任意一个元素）。
3.5 参数选择与优化细节
在实际写代码时，有几个参数和细节需要特别注意。
第一，pos数组的大小。如果元素值域是1到n，pos大小设为n+1。如果值域是0到n-1，pos大小设为n。如果值域不确定，可以用字典代替数组，但字典的常数因子更大，能不用就不用。
第二，二分查找的边界。bisect_left返回的是第一个大于等于x的位置。如果tails中所有元素都小于x，返回len(tails)，此时应该追加。这个逻辑在代码中已经处理了。
第三，输入规模。如果n达到10⁶，Python的input()和split()可能会比较慢，建议用sys.stdin.read()一次性读取。bisect模块是C实现的，速度很快，不用担心。
第四，内存占用。pos数组和tails数组各占O(n)空间，P数组其实可以省略，直接在遍历B时处理。这样空间从3个O(n)降到2个O(n)。
优化后的代码：
import sys import bisect def main(): data = sys.stdin.read().split() n = int(data[0]) A = list(map(int, data[1:n+1])) B = list(map(int, data[n+1:2*n+1])) pos = [0] * (n + 1) for i, x in enumerate(A): pos[x] = i tails = [] for x in B: v = pos[x] idx = bisect.bisect_left(tails, v) if idx == len(tails): tails.append(v) else: tails[idx] = v print(len(tails)) main()这个版本省去了P数组，直接在遍历B时计算pos[x]并处理，空间更省，速度也更快。
4. 常见问题与排查技巧实录
4.1 为什么我的答案比正确答案大
这是最常见的问题，通常是因为把严格上升当成了非严格上升。具体表现是用了bisect_right而不是bisect_left，或者在手动实现二分时条件写成了tails[mid] <= x。
举个例子：A = [1, 2]，B = [2, 1]。pos[1]=0, pos[2]=1。P = [1, 0]。严格上升的LIS长度是1（[1]或[0]），非严格上升的LIS长度也是1。这个例子看不出来。换一个：A = [1, 2, 3]，B = [1, 3, 2]。pos[1]=0, pos[2]=2, pos[3]=1。P = [0, 1, 2]。严格和非严格都是3。还是看不出来。
真正能看出区别的例子：A = [1, 2]，B = [1, 2]。pos[1]=0, pos[2]=1。P = [0, 1]。严格LIS是2，非严格也是2。好像都一样？
问题在于，当A和B都是排列时，P中的元素是0到n-1的一个排列，所有元素互不相同。所以严格上升和非严格上升在这个特殊情况下是等价的！因为不可能有两个相等的元素。那为什么还会有人在这里出错？
原因是：如果输入不保证是排列（比如有重复元素），P中就可能出现相等的元素，这时候严格和非严格的区别就体现出来了。但既然题目保证是排列，用哪个其实都对。不过为了代码的语义清晰，还是建议用bisect_left，明确表达"严格上升"的意图。
4.2 映射表构建时的越界问题
如果元素的值域不是1到n，而是0到n-1，pos数组的大小应该设为n，且pos[x]直接使用x作为下标。如果值域是1到n，pos大小设为n+1。如果值域更大（比如10⁹），就不能用数组了，必须用字典。
我见过有人在值域是1到n时把pos大小设为n，结果访问pos[n]时越界。这种错误在Python中会抛IndexError，在C++中则是未定义行为，可能不报错但结果错误，更难排查。
提示：在构建pos数组前，先确认元素的值域范围。如果不确定，用字典最安全，虽然慢一点但不会出错。
4.3 输入格式的坑
有些题目的输入可能不是标准的"n然后两行"，而是多组测试数据，或者n和序列在同一行。这时候用sys.stdin.read().split()一次性读取所有token，然后按顺序解析，是最稳妥的做法。不要用input()逐行读，因为行与行之间的划分可能和预期不一致。
还有一种情况是序列长度不相等。虽然题目说是两个排列，但万一输入有误，长度不等，代码可能会出错。可以在读取后加一个断言：assert len(A) == len(B) == n。这样出错时能快速定位。
4.4 性能瓶颈在哪里
对于n = 10⁶的规模，Python的纯循环可能会比较慢。主要的耗时在遍历B和二分查找。bisect是C实现的，二分部分很快。遍历B的循环是Python层面的，100万次循环大约需要0.1到0.2秒，可以接受。构建pos数组的循环也是100万次，类似。
如果还是超时，可以考虑用numpy做向量化操作，但numpy的searchsorted和bisect行为略有不同，需要仔细调整。一般来说，对于10⁶规模，上面的代码已经够用了。对于10⁷规模，Python可能就力不从心了，需要换C++。
4.5 常见问题速查表
| 问题现象 | 可能原因 | 排查方法 | 解决方案 |
|---|---|---|---|
| 答案偏大 | 用了非严格上升 | 检查二分条件 | 改用bisect_left |
| 答案偏小 | 映射表构建错误 | 打印pos数组检查 | 确认值域和下标对应 |
| 运行时报越界 | pos数组大小不足 | 检查最大值 | pos大小设为max+1 |
| 结果不稳定 | 输入有多组数据 | 检查读取逻辑 | 用read().split()统一读取 |
| 超时 | n太大或循环太慢 | 测n=10⁶的耗时 | 优化循环或换语言 |
| 答案完全错误 | 序列不是排列 | 检查是否有重复 | 确认题目条件 |
4.6 一个容易忽略的边界情况
当n=0时（空序列），LCS和LIS都是0。代码中如果n=0，pos数组大小为1，遍历B不执行，tails为空，输出0。正确。但有些题目可能不测n=0，所以这个边界容易被忽略。
当n=1时，pos数组大小为2，pos[A[0]]=0，遍历B得到P=[0]，tails=[0]，输出1。正确。
还有一个情况：如果A和B完全相同，LCS=n。此时P = [0, 1, 2, ..., n-1]，LIS=n。正确。如果A和B完全相反，LCS=1（假设n≥1）。此时P = [n-1, n-2, ..., 0]，LIS=1。正确。
这些边界情况在测试时都应该覆盖，确保代码的鲁棒性。
5. 从LCS到LIS转化的扩展思考
5.1 这个转化还能用在哪些场景
除了两个排列求LCS，这个转化还可以用在一些变体问题上。比如：给定两个序列，其中一个序列的元素互不相同（但不一定是1到n的排列），求LCS。这时候可以把第一个序列的元素映射为它的下标（用字典），然后遍历第二个序列，只保留在字典中出现的元素，生成位置序列，再求LIS。这样也能把复杂度从O(n²)降到O(n log n)。
再比如：求一个序列的最长公共子序列，其中公共子序列要求元素连续（即最长公共子串）。这个不能用LIS转化，因为子串要求连续，而LIS不要求连续。但可以用后缀自动机或哈希加二分来做。
还有一个相关的经典问题是"最长递增子序列的个数"，这个需要在LIS的基础上额外维护计数，稍微复杂一些，但核心思想还是贪心加二分。
5.2 为什么这个技巧在面试中常考
面试中考这个转化，主要考察三点：第一，对LCS和LIS两个基础算法的理解；第二，对排列性质的应用能力；第三，把一个问题转化为另一个已知问题的思维能力。这三点都是算法能力的核心。
我见过不少候选人能写出O(n²)的LCS，但被问到"如果两个序列都是排列，能不能优化"时就卡住了。其实只要提示"排列意味着每个元素唯一"，大部分人能想到映射的思路。关键是要有这个意识：看到特殊条件，就要想能不能利用它优化算法。
5.3 实现时的几个经验之谈
第一，能用库函数就用库函数。Python的bisect、C++的lower_bound都是经过高度优化的，比手写二分快且不容易出错。手写二分时边界条件很容易写错，比如while lo < hi还是while lo <= hi，hi = mid还是hi = mid - 1，这些细节一错就全盘皆输。
第二，先写暴力版本对拍。对于小规模数据，用O(n²)的DP算出正确答案，然后和O(n log n)的转化版本对比。如果两者一致，说明转化实现正确。这个对拍过程能发现很多隐藏的bug。
第三，注意常数的优化。虽然复杂度是O(n log n)，但如果常数太大，实际运行时间可能比预期长。比如用字典代替数组，虽然逻辑一样，但字典的哈希开销比数组索引大得多。在n=10⁶时，这个差距可能达到几倍。
第四，测试用例要覆盖各种情况：n=1、n=2、完全相同、完全相反、随机排列、有序排列、逆序排列。这些用例能覆盖大部分边界和逻辑分支。
5.4 一个实际项目中的教训
我之前在一个数据处理项目中遇到过类似的问题：需要比较两个用户的行为序列，找出最长的共同行为模式。两个序列都是用户的操作记录，每个操作有一个唯一ID。一开始我用的是O(n²)的LCS，数据量小的时候没问题，但用户量上来后，单次比较就要几秒钟，完全不可用。
后来发现操作ID是唯一的，而且两个序列的长度都不大（通常几十到几百），但比较次数非常多。我把LCS转化成了LIS，单次比较时间从毫秒级降到了微秒级，整体性能提升了两个数量级。这个经历让我深刻体会到：算法优化不是纸上谈兵，在实际系统中能带来实实在在的收益。
当然，那个项目里序列不一定是排列（因为用户可能重复执行同一个操作），所以我用的是"一个序列元素唯一"的弱化版本：把第一个序列的元素映射为下标，第二个序列中只保留在映射中出现的元素，然后求LIS。这个版本比严格的排列版本更通用，适用范围更广。
5.5 进一步优化的可能性
O(n log n)已经是比较排序下界决定的，不可能再低了（因为LIS问题可以归约到排序）。但如果序列有特殊性质，比如元素值域很小，可以用树状数组做到O(n log V)，其中V是值域。当V远小于n时，这个优化有意义。
还有一种情况是序列几乎有序，这时候可以用一些自适应算法，但实现复杂，收益不稳定，一般不建议。
对于绝大多数场景，O(n log n)的贪心加二分已经足够好了。代码简洁，常数小，不容易出错。这也是为什么这个算法成为LIS的标准解法。
6. 写在最后的一些个人体会
这个LCS转LIS的技巧，我最早是在一本算法竞赛的入门书上看到的。当时觉得这个转化很巧妙，但并没有真正理解它为什么成立。后来自己动手证明了等价性，又用代码实现了对拍，才算是真正掌握了。
我的体会是：算法学习不能只停留在"知道有这个技巧"的层面，必须深入到"为什么这个技巧成立"和"什么条件下这个技巧适用"。只有这样，遇到变体问题时才能灵活应对，而不是生搬硬套。
另外，实现细节的重要性怎么强调都不为过。同一个算法，不同的人写出来，性能可能差好几倍。二分查找的边界、数组的大小、输入读取的方式，这些看似琐碎的地方，往往决定了程序能否通过。我在实际写代码时，会习惯性地先写一个暴力版本作为基准，然后用优化版本对拍，确保正确性后再考虑性能优化。
最后分享一个小技巧：如果你在面试或比赛中一时想不起这个转化，可以先写O(n²)的DP拿到部分分，然后再尝试优化。很多时候，部分分和满分的差距就在这一个转化上。但即使拿不到满分，展示出清晰的思路和扎实的代码能力，也能给面试官留下好印象。
