Ravi Shankar Pandey
Longest Common Subsequence and Longest Increasing Subsequence
This is a classical LCS(Longest Common Subquence) problem can solved using Dynamic Programming method.
Using classical LCS Dynamic Programming algorihtm will have a complexity of O(N*N).
But with given constraints we can easily see that it will time out(TLE).
Since in this particular case the max possible number is 10^5 and each number comes only once in an array. We can easily convert this LCS problem to a LIS(Longest Increasing Subsequence) in the following way:-
first A3 stores the index of an element in A1
then A1 sotres the index of an element of A2 in A3
remove all non-zero elements of A1
then finally find LIS of A1
This aproach has run time complexity of O(nlog(n))
intialize an array A3 with all values as zero then for each i in A1 A3[A1[i]] = i; for each i in A2 A1[i] = A3[A2[i]] res = LIS(A1)