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;
}

Statistics

77% Solution Ratio
dip_BRUREarliest, Apr '20
nusuBotFastest, 0.0s
CodefresherLightest, 918 kB
mdalaminislamShortest, 447B
Toph uses cookies. By continuing you agree to our Cookie Policy.