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]
