这篇文章主要研究的是当最长公共子序列问题中，n达到1e5或以上级别时，如何巧妙使用与LIS相似的方法解决大n场景下的LCS问题。
关于最长上升子序列的两种解法，这里不会详细讲解，请读者熟知最长上升子序列的暴力和贪心解法后再来阅读本文。
对于大n而言直接使用LCS的暴力做法是n^2级别的，会超时，所以才有了接下来的思考，我们想想为什么说LCS也可以使用类似LIS的策略。
对于两个随机序列，我们要求它们的最长公共子序列，那么这两个随机序列一定是完全一样的数字组成的不同排列，或者说至少有一部分数字是一样的，组成的全排列，不然数字完全不一样根本不符合要求公共的这一条件。
A：3、2、1、4、5
B：1、2、3、4、5
以这两个序列为例，可知AB是拥有相同元素的两个不同排列，我们考虑先将第一个序列进行完全递增排序，这样可以保证第一个序列一定递增，然后由两个序列的子序列一定是A的子序列，而A本身单调递增，因此这个子序列就单调递增，换句话说在B中找到一个递增子序列，那么它在A中一定递增，而在B中找到最长上升子序列，即是答案。
如何实现？
将A序列按照递增排序这一过程并不是真的体现在代码里，它只是一种思想，我们需要用一个map来存储A数组中各个元素出现的位置编号，然后将其映射到B数组里，用这种思维举个具体的例子
用具体例子举例：首先将AB数组按照字母来代替数字，以完成较为直观的思维验证
A：a、b、c、d、e
B：c、b、a、d、e
就是说把A数组排序前B数组里各个元素在本来的A数组中出现的位置，写在B里，然后A进行排序，而在代码体现里为了方便直接记录起A数组各个元素的位置编号，然后直接使用B的映射即可，记录就是map[a[i]] = i; 而使用就是map[b[i]];
我们只需要在写代码时候有把A数组排序的这个思想就可以了，不用真的排序，因为用不到，我们是要求B数组的最长上升子序列，只需要用B数组，和map就可以了，A数组只是辅助作用。
#include <iostream>
#include <map>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n, f[N], a[N], b[N];
map<int, int> m;
/*
f存的是最长上升子序列是以哪个数字结尾的，这个数字在a数组的编号是什么
map存的是a数列里中各个数字在a中的位置
我们需要拿bi元素，去这个map里去查找，某个b序列的数字在a数组中的什么位置*/
int main()
{cin >> n;for (int i = 1; i <= n; ++ i ){cin >> a[i];m[a[i]] = i;}for (int i = 1; i <= n; ++ i ) cin >> b[i];memset(f, 0x3f, sizeof f);f[0] = 0;int len = 0;for (int i = 1; i <= n; ++ i ){int l = 0, r = len;/* 如果b在a数组中的位置大于此时最长上升长度len的结尾数字在a中映射那么让len++，因为我假设a数组是递增的，如果此时b元素在a数组中位置大于f【len】len是我们在b找到的最长上升子序列长度，而f[len]是代表len长度下以某个bi结尾的元素在a数组中的位置，此时的bi映射在a的位置更靠后，而且a又是递增，则说明找到一个更长的len于是进行更新。*/if (m[b[i]] > f[len]) f[ ++ len] = m[b[i]];else{/*f[len]是最长子序列的结尾数字在a中的编号，if没进去说明此时bi映射a中的位置没有len大但是这个bi可能可以更新其他长度的递增子序列结尾数字（此处请联系LIS更新策略）我们可以求出来中间某个上升子序列结尾数字在a中编号有没有可以被更新的，取最小值更新这个更新策略符合单调队列*/while (l < r){int mid = l + r >> 1;if (f[mid] > m[b[i]]) r = mid;else l = mid + 1;}f[r] = min(f[r], m[b[i]]);}}cout << len << endl;return 0;
}以上代码的注释应该可以帮助读者更加清晰的理解代码的用处。