COME ON CODE ON

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.

#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&#91;i&#93;).second)
        {
           k = s.find(A&#91;i&#93;);
           k++;
           if (k!=s.end())
              s.erase(k);
        }
    }
    return s.size();
}&#91;/sourcecode&#93;
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>
#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&#91;i&#93;,i)).second)
        {
           k = m.find(A&#91;i&#93;);
           l = k;
           k++;
           if (l==m.begin())
                  pre&#91;i&#93;=-1;
           else
           {
               l--;
               pre&#91;i&#93;=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

Advertisements

Written by fR0DDY

August 12, 2009 at 2:34 PM

36 Responses

Subscribe to comments with RSS.

  1. Great !!! keep it up.

    dumb_terminal

    September 8, 2009 at 10:20 PM

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

    rene

    November 15, 2009 at 3:05 AM

    • Can you be more specific?

      fR0D

      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(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);
    }
    }

    }

    rishabh

    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.

      fR0DDY

      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.

      fR0DDY

      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?

    shiv

    March 23, 2011 at 8:40 PM

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

      fR0DDY

      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 : 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…

    shiv

    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.

      fR0DDY

      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.

      fR0DDY

      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.

    nikhil

    May 22, 2012 at 2:32 PM

  13. Nice explaination dude….

    staticneo

    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

    Avneet

    October 2, 2013 at 4:53 PM

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

    tommyHU

    January 6, 2014 at 8:12 PM

    • You can just use a multi-set.

      multiset<int,greater<int> > s;

      fR0DDY

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

        tommyHU

        January 6, 2014 at 10:06 PM

    • I haven’t tried it but

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

      should work.

      fR0DDY

      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’

        tommyHU

        January 6, 2014 at 10:18 PM

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

        fR0DDY

        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 ?

    Jeremie

    February 22, 2014 at 7:09 PM

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

    prav

    September 30, 2015 at 2:38 AM

  21. 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/

    entri

    April 27, 2016 at 7:28 PM


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: