LIS is a short word of Longest Increasing Subsequence
In a n length of element of an array is present, while making an subsequence each element satisficed the condition of each element is bigger than the element before it
As an example
[6, 1, 3, 2, 8, 5, 9, 4]
from an array like this the longest increasing subsequence is
[1, 2, 8, 9], [1, 3, 8, 9] …
there is more increasing subsequence like [2, 5], [1, 9] but the longest ones are
[1, 2, 8, 9], [1, 3, 8, 9]
and the simplest way of making this algorithm is to using Dynamic Programming
Simple Example code
#include<stdio.h>
#include<algorithm>
using namespace std;
int len[1003],arr[1003];
int main()
{
int i,j,n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
for(i=0;i<n;i++){
len[i]=1;
for (j=0;j<i;j++){
if(arr[j]<arr[i]){
len[i]=max(len[i],len[j]+1);
}
}
}
return 0;
}This is a simple way of doing the LIS algorithm, but this way is simply just sweeping all of the array and updating the len array
and the condition for updating the len array is
Comparing of adding arr[i] on the end of len's i'th index and measure the length of the LIS and len[i]'s value
The bigger value is the new len[i]'s value
But the Time Complexity of this algorithm is O(n^2) so we need a more optimized method of coding this algorithm
for reduce the Time complexity here comes the Binary Search Algorithm
If you don't know the Binary Search Algorithm read this article first and comeback
Skuld Norniern
If we use the Binary Search Algorithm as our advantage we can find the place for the numbers using the Binary Search Algorithm
Binary Search Algorithm have a Time Complexity of O(log n) so if we use this than we can reduce the Time Complexity to O(nlog n)
arr [4, 3, 9, 11. 10]
g [4]
put the arr[0]'s value for the start
g [3]
we can find the place for the arr[1]'s value after doing the Binary Search Algorithm and that value is going to be the index for arr[1]
g [1, 3]
after that find the place for the arr[2]'s value, the g's last value is smaller than the arr[2] put the value to the back of that
g [1, 3, 11]
after that find the place for the arr[3]'s value, the g's last value is smaller than the arr[3] put the value to the back of that
g [1, 3, 9]
arr[4] is smaller than the last value of the g so find the place using the Binary Search we can find the index 2 and we can put the arr[4] in to that
#include<stdio.h>
#include<algorithm>
using namespace std;
int n, arr[40001], g[40001];
int bs(int l, int r, int t) {
int mid;
while(l<) {
mid=(l+r)/2;
if(g[mid]<t)l=mid+1;
else r=mid;
}
return r;
}
int main() {
int n,i,j=0,idx;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
g[0]=arr[0],i=1;
while(i<n) {
if(g[j]<arr[i]) g[j+1]=arr[i],j+=1;
else idx=bs(0,j,arr[i]),g[idx]=arr[i];
i += 1;
}
printf("%d",j+1);
return 0;
}