Longest Increasing Subsequence


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, consider subsequence {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

The Longest increasing subsequence is {0, 2, 6, 9, 11, 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.
 


 
We have already discussed a O(n2) time complexity solution of LIS here which uses Dynamic Programming. In this post, a O(nlogn) time Non-DP solution is discussed.
 

Let S[i] be defined as the smallest integer that ends an increasing sequence of length i. Now iterate through every integer X of the input set and do the following:

  • If X is more than the last element in S, then append X to the end of S. This essentially means we have found a new largest LIS.
     
  • Otherwise find the smallest element in S, which is more than or equal to X, and replace it with X. Because S is sorted at any time, the element can be found using binary search in log(N) time.

Let’s illustrate this with the help of a example. Consider below array of integers –

    {2, 6, 3, 4, 1, 2, 9, 5, 8}

Below are the steps followed by the algorithm –

Initialize to an empty set S = {}

Inserting 2 —- S = {2} – New largest LIS
Inserting 6 —- S = {2, 6} – New largest LIS
Inserting 3 —- S = {2, 3} – Replaced 6 with 3
Inserting 4 —- S = {2, 3, 4} – New largest LIS
Inserting 1 —- S = {1, 3, 4} – Replaced 2 with 1
Inserting 2 —- S = {1, 2, 4} – Replaced 3 with 2
Inserting 9 —- S = {1, 2, 4, 9} – New largest LIS
Inserting 5 —- S = {1, 2, 4, 5} – Replaced 9 with 5
Inserting 8 —- S = {1, 2, 4, 5, 8} – New largest LIS

 

So, the length of the LIS is 5 (the size of S). Please note that here S[i] is defined as the smallest integer that ends an increasing sequence of length i. Therefore, S does not represent an actual sequence but the size of S represents the length of the LIS.

Below solution uses std::set which is implemented as a red-black binary search tree which has a worst-case time complexity of O(logn) for insertion.

 
C++ implementation –
 

Download   Run Code

Output:

Length of LIS is 5

 

How to print LIS?

To make things simpler, we can keep in the S, not the actual integers, but their indices in the set. That is we do not keep {1, 2, 4, 5, 8}, but keep {4, 5, 3, 7, 8} since arr[4] = 1, arr[5] = 2, arr[3] = 4, arr[7] = 5 and arr[8] = 8.

To reconstruct the actual LIS we have to use a parent array. Let parent[i] be the predecessor of element with index i in the LIS ending at element with index i. If we update properly the parent array, the actual LIS is:

    arr[S[lastElementOfS]],
    arr[parent[S[lastElementOfS]]],
    arr[parent[parent[S[lastElementOfS]]]],

         ………………………………….
 

Below solution stores both actual integers and their indices in the set for easier implementation –

 

Download   Run Code

Output:

LIS is 2 3 4 5 8

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

References:
http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming
 

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
Sort by:   newest | oldest | most voted
Somil
Somil

nice.. short and concise code

Top Coder
Top Coder

clean and concise code..

Venkata
Venkata

Hi,
May i know what is the behavior if i am doing a — operation to a iterator pointing to the start of the set.

For example in the above code, if the set size is 1 and if i am doing (–it)->index; what is the behavior

wpDiscuz