最长公共子序列（上海交通大学考研机试题）

题目描述

给出两个长度为 n 的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复。

注意：
第一个序列中的所有元素均不重复。
第二个序列中可能有重复元素。
一个序列中的某些元素可能不在另一个序列中出现。

输入样例

5
2 1 3 8 7
2 9 3 4 5

输入样例

2

数据范围

$1\le n\le 10^6$, 序列内元素取值范围 $[1,10^6]$

分析

此题的数据量达到了1e6故不能用传统的$o(n^2)$的dp做法，需考虑$o(nlogn)$的做法。
由于第一个序列中元素不重复，这是一个典型的最长公共子序列转换为最长上升子序列问题。

---

最长上升子序列求法 $O(nlogn)$

首先我们看看最长公共子序列的求解过程是什么样子的？

A: 2 1 3 8 7
B: 2 9 3 4 5

ans = {2, 3};

就是从B中按照下标从小到大的顺序（从左至右）去A中找相同的数字，且在A中数字的下标也需要是递增的(也需要从左至右)

我们用另一种方式模拟这个过程

① 我们先将A中的数字和下标存储在idx数组中idx[key] = value,key 对应的是A中的值，value对应的是A中元素值对应的下标；

② 再按照坐标序遍历B中的元素，找到其在A中的位置idx[key], 找到一个我们就处理这个元素的下标到f数组中，将f数组维护为递增数组（刚刚我们说到A，B的子序列下标都需要是递增的）;

f 数组维护的是B数组元素在A数组元素中的下标

时间复杂度

$O(nlogn)$

C++ 代码

#include 

using namespace std;

const int N = 1e6 + 7;

int idx[N], f[N];
int cnt;
int n;

int find(int x) {
    int l = 0, r = cnt;
    while (l < r) {
        int mid = l + r >> 1;
        if (f[mid] >= x) r = mid;
        else l = mid + 1;
    }
    
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    memset(idx, -1, sizeof idx);
    
    for (int i = 1; i <= n; i ++ ) {
        int x;
        cin >> x;
        idx[x] = i;     // 记录数组中每个值的下标是多少
    }
    
    
    for (int i = 1; i <= n; i ++ ) {
        int x;
        cin >> x;
        
        int k = idx[x];
        if (k == -1) continue;
        
        if (k > f[cnt]) f[ ++ cnt ] = k;    // 如果当前下标大于f数组末尾元素下标就直接加入f数组
        else {
            int p = find(k);    // 找到大于等于k的第一个数的下标
            f[p] = k;           // 将下标的对应值替换掉
        }
    }
    
    cout << cnt << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52