# 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

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest

nice.. short and concise code

Guest
Top Coder

clean and concise code..

Guest

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

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

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

Guest

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

Should be:

Otherwise will crash in case of duplicate elements in sequence.