In this problem for finding LCS of two arrays, we are replacing the elements of first array based on the indices of second array. and then we are finding LIS on modified first array to get LCS of original arrays…i.e
Array1[] = {5,4,1,2,3}
Array2[] = {3,1,4,5,2} and after modification…
Array1[] = {4,3,2,5,1} can Anybody elaborate the logic behind this. Thanks.
ok, there is a problem on spoj , XMEN using this logic.
well , first thing about this logic is LCS of a random shuffled array and sorted array is LIS of that array
i guess you can agree with this…
LIS and sorted list is the longest sub sequence…
so this time we do the opposite… lcs is lis of shuffled array( sorted with modification)
EDITED
ok…
lets divide it into 2 parts
i give you a sorted array and a shuffled array you have to find LCS, right?
lets do it with an example…
s1 = 1 2 3 4 5 6
s2 = 6 2 3 4 1 5
so acc. to first statement … x = LCS(x1,x2) = LIS
so basically, LCS of these 2 string is also LIS of these 2 strings?
Agreed ?
(I am assuming yes if not, please tell i’ll elaborate more)
moving to next part…
2 array are given…
2 3 4 1 6 5
4 5 2 1 3 6
we need to sort one… on the basis of second…
lets sort second array, make 4 as 1’ , 5 as 2’ 2 as 3’ 1 as 4’ , 3 as 5’ and 6 as 6’… so second array is
1’ 2’ 3’ 4’ 5’ 6’
apply same transformation on first array… we get
3’ 5’ 1’ 4’ 6’ 2’
as transformation is applied on both arrays, answer will remain same 
,
so your question reduced to…
3 5 1 4 6 2
1 2 3 4 5 6
so solve it by finding LIS in (nlogn) Cheers
The first statement is clear but still I can’t get the second statement. so please can you make it some more clear…
i edited my answer
haha, your welcome my friend