每日算法挑战#5：最长公共子序列（LCS）优化解法

每日算法挑战 #5

最长公共子序列问题

给定两个长度为 n 的整数序列，目标是计算它们的最长公共子序列（LCS）的长度。特别地，第一个序列中的所有元素都是唯一的。

注意：

• 第一个序列的所有元素均唯一。
• 第二个序列中可能存在重复元素。
• 一个序列中的某些元素可能不会出现在另一个序列中。

输入格式

第一行包含一个整数 n，表示序列的长度。

接下来两行，每行包含 n 个整数，分别代表两个整数序列。

输出格式

输出一个整数，表示最长公共子序列的长度。

数据范围

1 ≤ n ≤ 1,000,000, 序列内元素取值范围 [1, 1,000,000]。

输入样例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

++++

思路解析：最初看到这个问题时，可能会认为它是一个简单的动态规划（DP）问题。然而，考虑到数据范围较大，直接使用 DP 方法并不高效。关键在于利用第一个序列中元素的唯一性，这使得我们可以将问题转化为寻找最长递增子序列（LIS）的问题。

具体来说，我们可以构建一个辅助数组 tar，记录第二个序列中每个元素在第一个序列中的位置。例如，在输入样例2中：

序列1：1 2 3 5 4

序列2：1 2 3 4 5

tar数组：1 2 3 5 4

我们观察到，tar 数组中的每个数字代表的是位置下标。如果我们在 tar 数组中找到最长递增子序列的长度，那么这个子序列在第一个序列中的相对顺序也是递增的。因此，原问题可以转化为求 tar 数组的 LIS。

由于 n 的范围较大（[1, 1,000,000]），我们不能使用 O(n²) 的 DP 方法来求解 LIS。相反，应该采用基于贪心和二分查找的 O(n log n) 解法。

以下是具体的 C++ 实现代码：

#include 
#include 
#include 
using namespace std;
const int N = 1000010;
int tar[N];
int n;
int q[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        tar[x] = i;
    }
    int len = 0;
    // 基于贪心通过二分解决
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        int k = tar[x];
        if (!k) continue; // 跳过未出现的数据
        int l = 0, r = len;
        while (l             int mid = l + r + 1 >> 1;
            if (q[mid]             else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = k;
    }
    printf("%d\n", len);
    return 0;
}