## Longest Increasing Subsequence (LIS)

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

For example for the sequence -7 10 9 2 3 8 8 1 the longest (strictly) increasing subsequence is -7 2 3 8 of length 4.

There are few methods to solve this question. The very first method is to sort the given sequence and save it into another array and then take out the longest common subsequence of the two arrays. This method has a complexity of O(*n*^{2}) which should be good for most question but not all.

We will see here an algorithm which take O(n log k) time where k is the size of the LIS. For explanation on this algorithm see Faster Algorithm on this page. Here’s a small code to calculate only the length of the LIS.

#include<iostream> #include<set> #include<vector> using namespace std; int LIS(vector<int> A) { int N = A.size(),i; set<int> s; set<int>::iterator k; for (i=0;i<N;i++) { if (s.insert(A[i]).second) { k = s.find(A[i]); k++; if (k!=s.end()) s.erase(k); } } return s.size(); }[/sourcecode] To also get the LIS we need to maintain a previous array which stores the index of the previous element in the LIS. Here's a C++ implementation. It returns the LIS as an array. [sourcecode language='cpp']#include<iostream> #include<map> #include<vector> using namespace std; typedef pair < int , int > PI; vector<int> LIS(vector<int> A) { int N = A.size(),i,j=-1,t; vector<int> pre(N,-1),res; map<int,int> m; map<int,int>::iterator k,l; for (i=0;i<N;i++) { if (m.insert(PI(A[i],i)).second) { k = m.find(A[i]); l = k; k++; if (l==m.begin()) pre[i]=-1; else { l--; pre[i]=l->second; } if (k!=m.end()) m.erase(k); } } k=m.end(); k--; j = k->second; while (j!=-1) { res.push_back(A[j]); j = pre[j]; } reverse (res.begin(),res.end()); return res; }

Note that if there are more than one LIS the above code prints the last one which occured in the input array. Also to get the LDS we just need to change the lines :

set<int> s; to set<int,greater<int> > s; and map<int,int> m; to map<int,int,greater<int> > m;

Also little changes need to be made to the above codes if you dont want the LIS to be strictly increasing and rather be Longest Non-Decreasing Subsequence or Longest Non-Increasing Subsequence.

Happy Coding!

-fR0D

Great !!! keep it up.

dumb_terminalSeptember 8, 2009 at 10:20 PM

im wondering how to modify it to get a LCS from abstract (but comparable) data…

reneNovember 15, 2009 at 3:05 AM

Can you be more specific?

fR0DNovember 16, 2009 at 12:21 PM

Can you tell me how to update this codes to be Longest Non-Decreasing Subsequence?

Ahmed AlyMarch 4, 2010 at 3:57 AM

I was trying a recursive approach…tho not tested this code on strong test cases !!

/*initially :: index == index of last element in array, max1==infinity*/

int LIS(int aa[], int index, int max1)

{

if(index==0){

if(aa[0]<max1) return 1;

else return 0;

}else{

if(aa[index]<max1){

return max((1+LIS(aa,(index-1),aa[index])),LIS(aa,(index-1),max1));

}else{

index–;

return LIS(aa,index,max1);

}

}

}

rishabhAugust 16, 2010 at 5:01 PM

Hi Rishabh,

We can always use the recursive approach, but it is not at all optimal. If you analyze your code, you can see that it will be very slow for larger values.

fR0DDYAugust 18, 2010 at 11:09 PM

Hi Frod,

I think the insert of map takes O(n) in best case. So, how it can be O(nlogn). Can you please take a look at it. Btw, nice blog with a good collection of question and nice solutions

Manish AgarwalFebruary 25, 2011 at 1:23 AM

Hi Manish,

No, a map is generally implementes as a self-balancing binary search tree, and hence the insertion time is O(log n). For more, look here.

fR0DDYFebruary 25, 2011 at 2:39 PM

in the first code you wrote here,to find the length of LIS ,the set left at the end contains LIS.I verified it with an example and it did. Is it always true? or mine was only a special case?

shivMarch 23, 2011 at 8:40 PM

No. It is not always the case. It might be LIS for some cases.

fR0DDYMarch 23, 2011 at 11:42 PM

But at the end of first LIS procedure you wrote, the set contains the elements in increasing order, and it’s size is equal to the length of LIS, so, shouldn’t the set itself be Longest Increasing Subsequence (since, it is longest as well as increasing)

Jatin (@jatinshridhar)October 2, 2013 at 2:20 PM

thanks fRODDY,

As you suggested ,I went through the section “faster algorithm” on the wikipedia link : http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

but i could not understand the last line there saying ” we can do a binary search for every single a1,a2…an “. can u please explain it ???

btw nice blog and it was really helpful to me…

shivMarch 25, 2011 at 7:33 PM

Hi fR0DDY,

Can you please explain 13th line “if (s.insert(A[i]).second)” ? What does s.insert(A[i]).second return?

Chetan GuptaSeptember 18, 2011 at 7:40 PM

set::insert returns a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element that already had its same value in the set. The pair::second element in the pair is set to true if a new element was inserted or false if an element with the same value existed.

fR0DDYSeptember 18, 2011 at 8:55 PM

how is 7 2 3 8 longest increasing sub-sequence

Sudeep Reddy G (@sudeepgaddam)October 6, 2011 at 2:28 AM

It is -7 2 3 8 and not 7 2 3 8.

fR0DDYOctober 6, 2011 at 10:10 AM

Hey, Nice post…

I had a question. In the first post shouldn’t it be

s.erase(–k); instead of s.erase(k);

as we have to erase the inserted element and we have done k++ once;

Siddharth BoraJanuary 7, 2012 at 9:51 PM

Yeah I realised my error

Siddharth BoraJanuary 7, 2012 at 10:22 PM

But could you tell me why you did this

if (k!=m.end())

m.erase(k);

in the second code

Siddharth BoraJanuary 7, 2012 at 10:34 PM

[…] can be done in 0(n-square) or 0(n log n ) time . The code for the 0(n log n) algorithm can be found here . If you are not very familiar with STL (in C++) , you may go for the 0(n-square) solution . Here […]

LCS and LIS ….. « Shivji Kumar JhaFebruary 8, 2012 at 12:04 AM

What’s the point of sharing this code, one can find better implementations online. What however is hard to find is an excellent explanation of the algorithm. It’d be better if you focused on that.

nikhilMay 22, 2012 at 2:32 PM

Nice explaination dude….

staticneoJanuary 17, 2013 at 1:57 AM

if the input is 4 2 3 won’t it return just 4

rishabh nigam (@rishabhnigam31)September 1, 2013 at 11:18 AM

very well thought out ~!

Aman PrakashSeptember 8, 2013 at 3:58 PM

can u explain it more

AvneetOctober 2, 2013 at 4:53 PM

Can you explain more on how to get Longest Non-Decreasing Subsequence?

tommyHUJanuary 6, 2014 at 8:12 PM

You can just use a multi-set.

fR0DDYJanuary 6, 2014 at 9:57 PM

I want to get the sub-sequence, too. It seems not right if directly replacing

map m;

by

multimap m;

tommyHUJanuary 6, 2014 at 10:06 PM

I haven’t tried it but

should work.

fR0DDYJanuary 6, 2014 at 10:15 PM

Still not work with multimap< int, int, greater > m;

Error 24 error C2039: ‘second’ : is not a member of ‘std::_Tree_iterator’

tommyHUJanuary 6, 2014 at 10:18 PM

This is a compilation error. You will have to figure it out. 🙂

fR0DDYJanuary 6, 2014 at 10:21 PM

Nice post, the implementation is very neat !!

How would you implement an algorithm that will print ALL the LISs ?

Is there a way to found out how many LISs exists without enumerating them ?

JeremieFebruary 22, 2014 at 7:09 PM

I Don’t understand the line

k++;

if (k!=s.end())

s.erase(k);

if we have inserted the element which is the last element of an active list of subsequence , then by doing k++ where are we reaching ???

Siddharth SinghAugust 15, 2015 at 4:50 PM

Is it because in a Binary Search Tree like Set a less valued node is on the left and an increment on the iterator means moving up to the parent node as there are no child of the less valued node ??

Siddharth SinghAugust 15, 2015 at 4:52 PM

can you explain how to get Longest Non decreasing subsequence in O(nlgn) time. I am struggling with it .

pravSeptember 30, 2015 at 2:38 AM

This page give an explanation on O(nlogn) algorithm, and very short code in C++: http://www.capacode.com/array/longest-increasing-subsequence-in-on-log-n-time/

entriApril 27, 2016 at 7:28 PM