This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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