## 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 *a*_{1}, *a*_{2}, …, *a*_{n} is called increasing, if *a*_{i}<*a*_{i+1} for *i*<*n*.The sequence *s*_{1}, *s*_{2}, …, *s*_{k} is called the subsequence of the sequence *a*_{1}, *a*_{2}, …, *a*_{n}, if there exist such a set of indexes 1 ≤ *i*_{1} < *i*_{2} < … < *i*_{k} ≤ *n* that *a*_{ij} = *s*_{j}. 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

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

fersarrFebruary 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 rajJune 28, 2017 at 11:20 PM

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

Thanks !

Piyush ChauhanMay 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.

fR0DDYMay 23, 2013 at 3:22 AM

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 bankaJanuary 28, 2014 at 10:37 AM

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

BobFebruary 16, 2016 at 12:12 PM

tks for your code. i got AC ^^

thienanhDecember 30, 2015 at 12:11 PM

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

BobJanuary 27, 2016 at 11:38 AM

Yes.

fR0DDYFebruary 2, 2016 at 2:27 PM

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

BobJanuary 27, 2016 at 11:42 AM