# COME ON CODE ON

A blog about programming and more programming.

## Longest Common Increasing Subsequence (LCIS)

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

Written by fR0DDY

June 1, 2010 at 12:47 PM

### 12 Responses

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

• Hey , even I’m trying this problem now and my approach is giving me wrong answer . Can you please share the input C5_3.in

bhishma raj

June 28, 2017 at 11:20 PM

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

• Yes.

fR0DDY

February 2, 2016 at 2:27 PM

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

Bob

January 27, 2016 at 11:42 AM

7. I cannot understand the step 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.”

I mean why to check only when A[i] > B[j] and why not when A[i] < B[j]?

Vivek Kumar Chaudhary

September 26, 2018 at 2:22 PM

8. I also want to know that why we checking when A[i] == B[j] that is cur + 1 > C[j]. Because, according to me, when A[i] == B[j] lenght of cis should increase by 1.

Vivek Kumar Chaudhary

September 26, 2018 at 3:29 PM