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
< ? php function GetCeilIndex ( $ arr , $ T , $ l , $ r , $ key ) { while ( $ r - $ l > 1 ) { $ m = ( int ) ( $ l + ( $ r - $ l ) / 2 ) ; if ( $ arr [ $ T [ $ m ] ] >= $ key ) $ r = $ m ; else $ l = $ m ; } return $ r ; } function LongestIncreasingSubsequence ( $ arr , $ n ) { $ tailIndices = array_fill ( 0 , $ n + 1 , 0 ) ; $ prevIndices = array_fill ( 0 , $ n + 1 , -1 ) ; $ len = 1 ; for ( $ 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 { $ pos = GetCeilIndex ( $ arr , $ tailIndices , -1 , $ len - 1 , $ arr [ $ i ] ) ; $ prevIndices [ $ i ] = $ tailIndices [ $ pos - 1 ] ; $ tailIndices [ $ pos ] = $ i ; } } echo " LIS ▁ of ▁ given ▁ input STRNEWLINE " ; for ( $ i = $ tailIndices [ $ len - 1 ] ; $ i >= 0 ; $ i = $ prevIndices [ $ i ] ) echo $ arr [ $ i ] . " ▁ " ; echo " STRNEWLINE " ; return $ len ; } $ arr = array ( 2 , 5 , 3 , 7 , 11 , 8 , 10 , 13 , 6 ) ; $ n = count ( $ arr ) ; print ( " LIS ▁ size ▁ " . LongestIncreasingSubsequence ( $ arr , $ n ) ) ; ? >