Skip to content

Instantly share code, notes, and snippets.

@iRajul

iRajul/LIS Secret

Last active August 29, 2015 14:02
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save iRajul/926affd9cc914228685f to your computer and use it in GitHub Desktop.
#include <iostream>
using namespace std;
//! @author : Rajul
//! code is poetry
//Program to find longest Increasing Subsequence in nlog(n) time
//! Function to do ceil binary search
//! Usage: To return either position of search's value or position of smallest
//! elememt in array which is greater then value of search
//! Here n = size of array small
int BinarySearch(int *arr,int *small,int n, int value)
{
int low = 0;
int high = n-1;
int mid;
while (low < high)
{
mid = low + ((high - low) / 2);
//! if array's mid value is greater then search value then select
//! high as mid , this is where we are making it a ceil binary search
if (arr[small[mid]] > value)
high = mid;
else if (arr[small[mid]] < value)
low = mid + 1;
else
return mid;// found
}
return low;// not found
}
//! function to print longest Increasing Subsequence with nlog(n) complexity
int LIS(int *arr, int n)
{
int *small = new int[n];
int *parent = new int[n];
int size = 0;
for(int i=0 ; i<n ;i++)
{
if(i == 0)
{
small[size] = i;
parent[i] = -1;
}
//! Find the "index" of the smallest element in array small, which is >=than X,
//! and change it to X. Here parent[indexOfX] = S[index - 1].
else if(arr[i] <= arr[small[size]])
{
int pos = BinarySearch(arr,small,size+1,arr[i]);
small[pos] = i;
parent[i] = small[pos-1];
}
//! parent[indexOfX] = Last Element Of S
else
{
size = size+1;
small[size] = i;
parent[i] = small[size-1];
}
}
cout<<"Length of Longest Increasing Subsequence = "<<size+1<<endl;
int pos = small[size];
//! print Longest Increasing Subsequence
while(pos not_eq -1)
{
cout<<arr[pos]<<endl;
pos = parent[pos];
}
}
int main( )
{
int arr[] = {2,6,3,2,4,6,9,5,8};
unsigned int size = sizeof(arr)/sizeof(int);
LIS(arr,size);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment