Prince and Princess

Problem

Idea : Given two number sequence . You have to find out the LCS of the two . But you can not use the normal LCS finding algorithm .

You have to find out LCS using LIS . You can learn LIS from here

For a single sequence of number , we can calculate LIS as below -

Push the first element in a vector . Then , if the number is greater then the top element of the vector , push it also , else find out its position of the vector using binary search . Then put it in the position .

Then the LIS is the size of vector .

But for two sequence ?

We only take the element that are present in both sequence . To maintain increasing sequence , we may indexing the first sequence from 1 .

Then in second sequenec , we cheak whether it whether it present in first sequence or not . If it is not present , skip it . The first value that is present in both sequence , push it in a vector . Then if the index of next element is greater than the index of the last element of vector , push it . Else , find out the position of the index in the vector and put it .

Finally , the size of vector is our answer .

My Solution