 # ACMICL4 - Editorial

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

#### Author:

Ravi Shankar Pandey

Shubham Gupta

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)
```
2 Likes