LIS Algorithm

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

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;
}