### PROBLEM LINK:

http://www.codechef.com/ICL2015/problems/ACMICL4

#### Author:

Ravi Shankar Pandey

#### Tester:

Shubham Gupta

#### DIFFICULTY:

MEDIUM-HARD

#### PREREQUISITES:

Longest Common Subsequence and Longest Increasing Subsequence

#### EXPLANATION:

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))

#### SOLUTION:

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)