# 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.

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 –

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

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 🙂

Get great deals at Amazon

Subscribe
Notify of
Guest
Somil

nice.. short and concise code

Guest
Top Coder

clean and concise code..

Guest
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

Guest
Appun

In your explanation above LIS of {2,6,3,4,1,2,9,5,8} = {1,2,4,5,8}, but “4” is out of place, shouldn’t the output = {1,2,5,8}?

Guest
Appun

Slightly modified java version
http://ideone.com/bvpht2

Guest
Tom K.

Since we are usually replacing an element in the set, and sometimes increasing the size by pushing a new element onto the end, using a sorted vector (or deque) instead of a set would probably be better. It’s identical in code length and big O, but in practice is going to use less memory and will almost certainly have a faster execution time for any input.

Guest
Roman

Should be:

Otherwise will crash in case of duplicate elements in sequence.