Longest Increasing Subsequence using LCS

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

 


For example, the longest increasing subsequence is [0, 2, 6, 9, 11, 15] in below Subsequence –

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

This subsequence has length 6; the input sequence has no 7-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,

[0, 4, 6, 9, 11, 15] or [0, 4, 6, 9, 13, 15]

are other increasing subsequences of equal length in the same input sequence.

 


 

In the previous post, we have discussed a Dynamic Programming solution to solve longest increasing subsequence problem. In this post another interesting DP solution is discussed which we reduce Longest Increasing Subsequence (LIS) to Longest Common Subsequence (LCS). Below is the complete algorithm –

  • Create a copy of the original array
  • Sort the copy of the original array
  • Remove all the duplicates from the copy
  • Perform LCS of original sequence with its modified copy

C++

Download   Run Code

Output:

The length of LIS is 6

How to read out an LIS?

The idea is to read LCS lookup table and follow the path from the bottom right to the top left corner of the table. If the current element in X and Y are equal, then they are part of the LIS and we move diagonally. If the current element in X and Y are different, we go up or left, depending on which cell has a higher number.

C++

Download   Run Code

Output:

The LIS is 0 2 6 9 11 15

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz