Construction of Longest Increasing Subsequence ( N log N ) | 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
function GetCeilIndex ( arr , T , l , r , key ) { while ( r - l > 1 ) { let m = l + parseInt ( ( r - l ) / 2 , 10 ) ; if ( arr [ T [ m ] ] >= key ) r = m ; else l = m ; } return r ; } function LongestIncreasingSubsequence ( arr , n ) { let tailIndices = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) tailIndices [ i ] = 0 ; let prevIndices = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) prevIndices [ i ] = - 1 ; let len = 1 ; for ( let 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 { let pos = GetCeilIndex ( arr , tailIndices , - 1 , len - 1 , arr [ i ] ) ; prevIndices [ i ] = tailIndices [ pos - 1 ] ; tailIndices [ pos ] = i ; } } document . write ( " " + " " ) ; for ( let i = tailIndices [ len - 1 ] ; i >= 0 ; i = prevIndices [ i ] ) document . write ( arr [ i ] + " " ) ; document . write ( " " ) ; return len ; } let arr = [ 2 , 5 , 3 , 7 , 11 , 8 , 10 , 13 , 6 ] ; let n = arr . length ; document . write ( " " + LongestIncreasingSubsequence ( arr , n ) ) ;