First we need to observe that array $A$
and $B$
are permutations of $1$
to $n$
. So we can map $A$
in $1$
to $n$
and then take input $B$
as $1$
to $n$
maping of $A$
. Now we can see that finding "Longest Common Subsequence" was no different than finding "Longest Increasing Subsequence" of array $B$
. And luckily it can be done in $O(nlog{n})$
complexity.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a,b,m[n+1],x;
vector <int> v;
for(int i=1;i<=n;i++){
cin>>a;
m[a]=i;
}
for(int i=0;i<n;i++){
cin>>b;
x=m[b];
vector <int>::iterator it=lower_bound(v.begin(),v.end(),x);
if(it==v.end())
v.push_back(x);
else
v[it-v.begin()]=x;
}
int ans=v.size();
cout<<ans;
return 0;
}