A blog about programming and more programming.

Longest Increasing Subsequence (LIS)

with 36 comments

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(n2) 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.

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&#91;i&#93;).second)
           k = s.find(A&#91;i&#93;);
           if (k!=s.end())
    return s.size();
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.
&#91;sourcecode language='cpp'&#93;#include<iostream>
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&#91;i&#93;,i)).second)
           k = m.find(A&#91;i&#93;);
           l = k;
           if (l==m.begin())
           if (k!=m.end())
    j = k->second;
    while (j!=-1)
          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;
set<int,greater<int> > s;
map<int,int> m;
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!


Written by fR0DDY

August 12, 2009 at 2:34 PM

36 Responses

Subscribe to comments with RSS.

  1. Great !!! keep it up.


    September 8, 2009 at 10:20 PM

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


    November 15, 2009 at 3:05 AM

    • Can you be more specific?


      November 16, 2009 at 12:21 PM

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

    Ahmed Aly

    March 4, 2010 at 3:57 AM

  4. 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(aa[0]<max1) return 1;
    else return 0;
    return max((1+LIS(aa,(index-1),aa[index])),LIS(aa,(index-1),max1));
    return LIS(aa,index,max1);



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


      August 18, 2010 at 11:09 PM

  5. 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 Agarwal

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


      February 25, 2011 at 2:39 PM

  6. 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?


    March 23, 2011 at 8:40 PM

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


      March 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

  7. thanks fRODDY,
    As you suggested ,I went through the section “faster algorithm” on the wikipedia link :
    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…


    March 25, 2011 at 7:33 PM

  8. Hi fR0DDY,

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

    Chetan Gupta

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


      September 18, 2011 at 8:55 PM

  9. how is 7 2 3 8 longest increasing sub-sequence

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


      October 6, 2011 at 10:10 AM

  10. 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 Bora

    January 7, 2012 at 9:51 PM

  11. […] 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 […]

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


    May 22, 2012 at 2:32 PM

  13. Nice explaination dude….


    January 17, 2013 at 1:57 AM

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

  15. very well thought out ~!

    Aman Prakash

    September 8, 2013 at 3:58 PM

  16. can u explain it more


    October 2, 2013 at 4:53 PM

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


    January 6, 2014 at 8:12 PM

    • You can just use a multi-set.

      multiset<int,greater<int> > s;


      January 6, 2014 at 9:57 PM

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

        map m;


        multimap m;


        January 6, 2014 at 10:06 PM

    • I haven’t tried it but

      multimap<int,int,greater<int> > m;

      should work.


      January 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’


        January 6, 2014 at 10:18 PM

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


        January 6, 2014 at 10:21 PM

  18. 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 ?


    February 22, 2014 at 7:09 PM

  19. I Don’t understand the line
    if (k!=s.end())

    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 Singh

    August 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 Singh

      August 15, 2015 at 4:52 PM

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


    September 30, 2015 at 2:38 AM

  21. This page give an explanation on O(nlogn) algorithm, and very short code in C++:


    April 27, 2016 at 7:28 PM

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: