可以发现只有当两个序列中都没有重复元素时（1～n的排列）此种优化才是高效的，不然可能很不稳定。
求a[] 与b[]中的LCS
通过记录lis[i]表示a[i]在b[]中的位置，将LCS问题转化为最长上升子序列问题，转化方法如下：
for(int i=1;i<=n;i++){
local[b[i]]=i;
}
for(int i=1;i<=n;i++){
lis[i]=local[a[i]];
}
当序列中有元素重复时，我们们需要保证对于每个a[i]所记录的位置必须是逆序的，以保证一个元素只取一次。
例：举例说明：
A：abdba
B：dbaaba
则1：先顺序扫描A串，取其在B串的所有位置：
2：a(2,3,5) b(1,4) d(0)。
3：用每个字母的反序列替换，则最终的最长严格递增子序列的长度即为解。
替换结果：532 41 0 41 532
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int read(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return fh*rv;
}
int n,a[100005],b[100005],local[100005],lis[100005],dp[100005];
int main(){
freopen("in.txt","r",stdin);
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
b[i]=read();
}
for(int i=1;i<=n;i++){
local[b[i]]=i;
}
for(int i=1;i<=n;i++){
lis[i]=local[a[i]];
}
dp[1]=lis[1];dp[0]++;
for(int i=2;i<=n;i++){
int l=1,r=dp[0],m=0;
while(l<=r){
m=(l+r)>>1;
if(dp[m]<=lis[i]){
l=m+1;
}else r=m-1;
}
if(l==1){
dp[l]=min(dp[l],lis[i]);
}else {
if(l==dp[0]+1){
dp[0]++;
dp[l]=lis[i];
}else {
dp[l]=min(dp[l],lis[i]);
}
}
}
cout<<dp[0];
fclose(stdin);
return 0;
}