A Daily Topic # 5
最长公共子序列
给出两个长度为 n 的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复。
注意：
- 第一个序列中的所有元素均不重复。
- 第二个序列中可能有重复元素。
- 一个序列中的某些元素可能不在另一个序列中出现。
输入格式
第一行包含一个整数 n。
接下来两行，每行包含 n 个整数，表示一个整数序列。
输出格式
输出一个整数，表示最长公共子序列的长度。
数据范围
1≤n≤1e6,
序列内元素取值范围 [1, 1e6]。
输入样例1：
5
1 2 3 4 5
1 2 3 4 5
输出样例1：
5
输入样例2：
5
1 2 3 5 4
1 2 3 4 5
输出样例2：
4
++++
思路：第一眼没看数据范围，以为就是个简单的LCS DP问题，然后看到数据范围知道不可取。然后有个很重要的条件就是第一个序列是不重复的一个序列，所以这就使得序列二的数字出现在序列一中的位置是固定的。我们拿输入样例2来讲：
其中tar数组表示序列二的数字在序列一中出现的位置。
序列1： 1 2 3 5 4
序列2： 1 2 3 4 5
tar数组：1 2 3 5 4
然后我们观察tar数组，每个数字代表的是位置下标，如果我们找到tar数组的最长上升子序列长度，1 2 3 4 或者1 2 3 5。因为是上升的，所以得到的在序列一中的位置的数字一定也是如此的次序，又因为tar数组是描述序列二的性质的数组，所以其次序一定是从左到右的。因此我们就可以把LCS问题转化成LIS问题，即求tar数组的最长上升子序列问题。但是观察n的范围是[1, 1e6],通过DP求最长上升子序列是O(n²)的复杂度，因此不可取。应该用基于贪心的O(nlogn)的解法。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int tar[N];
int n;
int q[N];
int main()
{
scanf("%d", &n);
int x;
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &x);
tar[x] = i;
}
int len = 0;
//基于贪心通过二分解决
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &x);
int k = tar[x];
if (!k) continue;//跳过没有出现过的数据
int l = 0, r = len;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] < k) l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = k;
}
printf("%d
", len);
return 0;
}