Construction of Longest Increasing Subsequence ( N log N ) | C ++ implementation to find longest increasing subsequence in O ( n Log n ) time . ; Binary search ; Add boundary case , when array n is zero Depend on smart pointers ; initialized with - 1 ; it will always point to empty location ; new smallest value ; arr [ i ] wants to extend largest subsequence ; arr [ i ] wants to be a potential condidate of future subsequence It will replace ceil value in tailIndices ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int GetCeilIndex ( int arr [ ] , vector < int > & T , int l , int r , int key ) { while ( r - l > 1 ) { int m = l + ( r - l ) / 2 ; if ( arr [ T [ m ] ] >= key ) r = m ; else l = m ; } return r ; } int LongestIncreasingSubsequence ( int arr [ ] , int n ) { vector < int > tailIndices ( n , 0 ) ; vector < int > prevIndices ( n , -1 ) ; int len = 1 ; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] < arr [ tailIndices [ 0 ] ] ) { tailIndices [ 0 ] = i ; } else if ( arr [ i ] > arr [ tailIndices [ len - 1 ] ] ) { prevIndices [ i ] = tailIndices [ len - 1 ] ; tailIndices [ len ++ ] = i ; } else { int pos = GetCeilIndex ( arr , tailIndices , -1 , len - 1 , arr [ i ] ) ; prevIndices [ i ] = tailIndices [ pos - 1 ] ; tailIndices [ pos ] = i ; } } cout << " LIS ▁ of ▁ given ▁ input " << endl ; for ( int i = tailIndices [ len - 1 ] ; i >= 0 ; i = prevIndices [ i ] ) cout << arr [ i ] << " ▁ " ; cout << endl ; return len ; } int main ( ) { int arr [ ] = { 2 , 5 , 3 , 7 , 11 , 8 , 10 , 13 , 6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printf ( " LIS ▁ size ▁ % d STRNEWLINE " , LongestIncreasingSubsequence ( arr , n ) ) ; return 0 ; }