详解最长公共子序列问题（三种方法）

这里，为了更方便地解释，我以洛谷上的一道典型题目为例，为大家讲解处理最长公共子序列问题的几种常见方法。这道题目中规定了两个子序列的长度相等，如果遇到不等的情况，也只需要对长度稍作修改即可，算法思想不变。

题目描述

给出 1，2，…… ，n 的两个排列 A 和 B ，求它们的最长公共子序列。

输入格式

第一行是一个数 n。

接下来两行，每行为 n 个数，为自然数 1，2，…… ，n 的一个排列。

输出格式

一个数，即最长公共子序列的长度。

样例输入 

5 

3 2 1 4 5

1 2 3 4 5

样例输出 

3

提示

- 对于 50% 的数据， n n; for (int i = 1; i > A[i]; } for (int i = 1; i > B[i]; } for (int i = 1; i B[i]; } int ans = 0, t; for (int i = 1; i 4，5 -> 5；然后B按照A的转化规则进行转化，于是变成：

A: 1 2 3 4 5

B: 3 2 1 4 5

这样标号之后，序列的长度显然不会改变。但是出现了一个性质：两个序列的子序列，一定是A的子序列。而A本身就是递增的，因此这个子序列是递增的。换句话说，只要这个子序列在B中递增，它就是A的子序列。于是，问题就转化成了求B中的最长递增子序列。

你可能觉得这样的转化多此一举，但请注意，解决最长递增子序列类问题，时间复杂度最低可以达到 O(nlogn)；也就是说，用这种方法，我们可以将求解最长公共子序列问题的时间复杂度降为O(nlogn)，这样在处理相关问题时就可以避免时间超限的情况。

但新的问题又来了，怎么在O(nlogn)时间复杂度内求解最长递增子序列问题？这里，我参考了别人给出的一个解释：

我们以数列 5 2 3 1 4 为例

首先，把 5 加入答案序列中，然后遍历到 2，发现 22，所以直接把3加到答案序列中，这时候就是 [2,3] ;然后遍历到1，我们发现1> n; int a; for (int i = 1; i > a; m[a] = i; } int b; for (int i = 1; i > b; //按照A的转化规则，转化B B[i] = m[b]; } //序列C用于保存当前的最优解 vectorC; C.push_back(0); int len = 0; //保存最终结果 for (int i = 1; i C[len]) { C.push_back(B[i]); len++; } else { C[lower_bound(C.begin(), C.end(), B[i]) - C.begin()] = B[i]; } } cout