Given a sequence of numbers,we need to find the longest increasing sub-sequence from the given input(not necessary continuous).
Example-
Input- 1 10 4 5 3 2 9 11 13
Increasing Sub-sequences-
1 4 5
5 9 11 13
10 11 13
4 5 9,etc
Longest Increasing Sub-sequence– 1 4 5 9 11 13
Length of Longest Increasing Sub-sequence(LIS) – 6
Naive Algorithm-
Check all the sub-sequences,but its time complexity will be approximately O(n^2) where n is the number of elements.
Efficient Algorithm-
x[] is the input sequence.Let it be 1 10 4 5 3 2 9 11 13.
The first element to be added in m[] is the first element of the input sequence.
Each element of the input sequence is taken one by one.
1. If it is greater than or equal to the last element of m[],insert the element in m[] at the end.
2. Else,replace the element in m[] which is just greater than element of the input sequence with the selected element of the input sequence.
Finally,the length of the array m[] is the length of the longest increasing sub-sequence.
Note-Elements of m[] are not elements of LIS.The actual values in the sub-sequence can be found by storing them in another array during the loop.
Illustration-
m=[]
m=[1]
m=[1 10]
m=[1 4] // 10 is replaced by 4 as number just greater than 4 is 10.
m=[1 4 5]
m=[1 3 5] //4 is replaced by 3 as number just greater than 3 is 4.
m=[1 2 5] //3 is replaced by 2 as number just greater than 2 is 3.
m=[1 2 5 9]
m=[1 2 5 9 11]
m=[1 2 5 9 11 13]
Thus,length of LIS is 6,that is size of m[].
Code-
[cpp]
m[1]=a[0];
p=2;
for(i=1;i<n;i++)
{
s=1;
//finding element just greater than x[i]
for(j=1;j<p;j++)
{
if(x[i]<m[j])
{
m[j]=x[i];s=0;break;
}
}
//value of s determines if element just greater than
// x[i] is found or not.
//If not found,then it is inserted at the end.
if(s==1){m[p]=x[i];p++;}
//p-1 is the size of the array and
// thus the length of LIS.
}
[/cpp]
Sreekumar (KJ) has been a hobby programmer from school days. Codemarvels is his personal blog from the year 2010, where he writes about technology, philosophy, society and a bit about physics.
He now runs a conversational AI company – DheeYantra – focusing his efforts to help businesses improve operational efficiency using digital employees powered by AI.