Longest Bitonic Subsequence | DP | lbs ( ) returns the length of the Longest Bitonic Subsequence in arr [ ] of size n . The function mainly creates two temporary arrays lis [ ] and lds [ ] and returns the maximum lis [ i ] + lds [ i ] - 1. lis [ i ] == > Longest Increasing subsequence ending with arr [ i ] lds [ i ] == > Longest decreasing subsequence starting with arr [ i ] ; Allocate memory for LIS [ ] and initialize LIS values as 1 for all indexes ; Compute LIS values from left to right ; Allocate memory for lds and initialize LDS values for all indexes ; Compute LDS values from right to left ; Return the maximum value of lis [ i ] + lds [ i ] - 1 ; Driver Code
< ? php function lbs ( & $ arr , $ n ) { $ lis = array_fill ( 0 , $ n , NULL ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ lis [ $ i ] = 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) for ( $ j = 0 ; $ j < $ i ; $ j ++ ) if ( $ arr [ $ i ] > $ arr [ $ j ] && $ lis [ $ i ] < $ lis [ $ j ] + 1 ) $ lis [ $ i ] = $ lis [ $ j ] + 1 ; $ lds = array_fill ( 0 , $ n , NULL ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ lds [ $ i ] = 1 ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) for ( $ j = $ n - 1 ; $ j > $ i ; $ j -- ) if ( $ arr [ $ i ] > $ arr [ $ j ] && $ lds [ $ i ] < $ lds [ $ j ] + 1 ) $ lds [ $ i ] = $ lds [ $ j ] + 1 ; $ max = $ lis [ 0 ] + $ lds [ 0 ] - 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) if ( $ lis [ $ i ] + $ lds [ $ i ] - 1 > $ max ) $ max = $ lis [ $ i ] + $ lds [ $ i ] - 1 ; return $ max ; } $ arr = array ( 0 , 8 , 4 , 12 , 2 , 10 , 6 , 14 , 1 , 9 , 5 , 13 , 3 , 11 , 7 , 15 ) ; $ n = sizeof ( $ arr ) ; echo " Length ▁ of ▁ LBS ▁ is ▁ " . lbs ( $ arr , $ n ) ; ? >