https://www.acwing.com/problem/content/3513/

 

 其中一个串不重复是公共子序列问题转换为上升子序列问题的一个充要条件。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int q[N],id[N];
int main()
{
    int n;
    cin>>n;
    memset(id,-1,sizeof id);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        id[x]=i;
    }
    int tt=0;
    q[0]=-1;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        int k=id[x];
        if(k==-1) continue;
        int l=0,r=tt;
        while(l<r){//找到小于k的最大的
            int mid=l+r+1>>1;
            if(q[mid]>=k) r=mid-1;
            else l=mid;
        }
        q[r+1]=k;
        tt=max(tt,r+1);
    }
    cout<<tt<<endl;
    return 0;
}