COME ON CODE ON

A blog about programming and more programming.

Longest Common Increasing Subsequence (LCIS)

with 9 comments

Given 2 sequences of integers, we need to find a longest sub-sequence which is common to both the sequences, and the numbers of such a sub-sequence are in strictly increasing order.
For example,
2 3 1 6 5 4 6
1 3 5 6
the LCIS is 3 5 6.

The sequence a1, a2, …, an is called increasing, if ai<ai+1 for i<n.The sequence s1, s2, …, sk is called the subsequence of the sequence a1, a2, …, an, if there exist such a set of indexes 1 ≤ i1 < i2 < … < ik ≤ n that aij = sj. In other words, the sequence s can be derived from the sequence a by crossing out some elements.

A nice tutorial on the algorithm is given on CodeChef blog here. If you read the blog you can see that instead of looking for LCIS in a candidate matrix, we can keep an array that stores the length of LCIS ending at that particular element. Also we keep a lookup previous array that gives the index of the previous element of the LCIS, which is used to reconstruct the LCIS.

For every element in the two arrays
1> If they are equal we check whether the LCIS formed will be bigger than any previous such LCIS ending at that element. If yes we change the data.
2> If the jth element of array B is smaller than ith element of array A, we check whether it has a LCIS greater than current LCIS length, if yes we store it as previous value and it’s LCIS length as current LCIS length.

Here’s a C++ code.

#include<iostream>
using namespace std;
#include<vector>

void LCIS(vector<int> A, vector<int> B)
{
    int N=A.size(),M=B.size(),i,j;
    vector<int> C(M,0);
    vector<int> prev(M,0);
    vector<int> res;
    
    for (i=0;i<N;i++)
    {
        int cur=0,last=-1;
        for (j=0;j<M;j++)
        {
            if (A[i]==B[j] && cur+1>C[j])
            {
               C[j]=cur+1;
               prev[j]=last;
            }
            if (B[j]<A[i] && cur<C[j])
            {
               cur=C[j];
               last=j;
            }
        }
    }
    
    int length=0,index=-1;
    for (i=0;i<M;i++)
        if (C[i]>length)
        {
           length=C[i];
           index=i;
        }
    printf("The length of LCIS is %d\n",length);
    if (length>0)
    {
       printf("The LCIS is \n");
       while (index!=-1)
       {
             res.push_back(B[index]);
             index=prev[index];
       }
       reverse(res.begin(),res.end());
       for (i=0;i<length;i++)
           printf("%d%s",res[i],i==length-1?"\n":" ");
    }
}


int main()
{
    int n,m,i;
    scanf ("%d", &n);
    vector<int> A(n,0);
    for (i = 0; i < n; i++)
        scanf ("%d", &A[i]);
    scanf ("%d", &m);
    vector<int> B(m,0);
    for (i = 0; i < m; i++)
        scanf ("%d", &B[i]);
    LCIS(A,B);
}

NJOY!
-fR0DDY

Advertisements

Written by fR0DDY

June 1, 2010 at 12:47 PM

9 Responses

Subscribe to comments with RSS.

  1. Hey! thanks for this idea! I really looked into it and thought it was nice but now I dont think its correct! For example, the while loop that starts on line 41 does 88 iterations using input C5_3.in but the FOR LOOP in line 47 does 84 iterations since LCIS length is 84. I have submitted the algorithm to PKU (http://poj.org/problem?id=2127) and it gets wrong answer. Also, it times out in Code Chef

    fersarr

    February 15, 2013 at 5:33 AM

  2. Submitted this code for uva 12511 – Virus , works like a charm.
    Thanks !

    Piyush Chauhan

    May 22, 2013 at 11:58 PM

    • There’s no point in submitting my code if you don’t understand it. Please try to understand the algorithm and code it yourself if you really want to improve.

      fR0DDY

      May 23, 2013 at 3:22 AM

  3. Hi fRODDY, This was a very well implemented code. But like my code, your code also gives WA on this judge http://poj.org/problem?id=2127 . Please try submitting the code yourself with the extra formatting removed to yourself see if your code gives AC.

    nikunj banka

    January 28, 2014 at 10:37 AM

    • Did you ever get this code working for that online judge?

      Bob

      February 16, 2016 at 12:12 PM

  4. tks for your code. i got AC ^^

    thienanh

    December 30, 2015 at 12:11 PM

  5. Is the time complexity of your implementation simply O(n^2)?

    Bob

    January 27, 2016 at 11:38 AM

  6. Is the time complexity of this simply O(n^2)?

    Bob

    January 27, 2016 at 11:42 AM


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: