Print Longest Bitonic subsequence ( Space Optimized Approach ) | Function to print the longest bitonic subsequence ; Function to generate the longest bitonic subsequence ; Store the lengths of LIS ending at every index ; Store the lengths of LDS ending at every index ; Compute LIS for all indices ; Compute LDS for all indices ; Find the index having maximum value of lis [ i ] + lds [ i ] - 1 ; Stores the count of elements in increasing order in Bitonic subsequence ; Store the increasing subsequence ; Sort the bitonic subsequence to arrange smaller elements at the beginning ; Stores the count of elements in decreasing order in Bitonic subsequence ; Print the longest bitonic sequence ; Driver Code
function printRes ( res ) { var n = res . length ; for ( var i = 0 ; i < n ; i ++ ) { document . write ( res [ i ] + " " ) ; } } function printLBS ( arr , N ) { var lis = Array ( N ) ; var lds = Array ( N ) ; for ( var i = 0 ; i < N ; i ++ ) { lis [ i ] = lds [ i ] = 1 ; } for ( var i = 0 ; i < N ; i ++ ) { for ( var j = 0 ; j < i ; j ++ ) { if ( arr [ j ] < arr [ i ] ) { if ( lis [ i ] < lis [ j ] + 1 ) lis [ i ] = lis [ j ] + 1 ; } } } for ( var i = N - 1 ; i >= 0 ; i -- ) { for ( var j = N - 1 ; j > i ; j -- ) { if ( arr [ j ] < arr [ i ] ) { if ( lds [ i ] < lds [ j ] + 1 ) lds [ i ] = lds [ j ] + 1 ; } } } var MaxVal = arr [ 0 ] , inx = 0 ; for ( var i = 0 ; i < N ; i ++ ) { if ( MaxVal < lis [ i ] + lds [ i ] - 1 ) { MaxVal = lis [ i ] + lds [ i ] - 1 ; inx = i ; } } var ct1 = lis [ inx ] ; var res = [ ] ; for ( var i = inx ; i >= 0 && ct1 > 0 ; i -- ) { if ( lis [ i ] == ct1 ) { res . push ( arr [ i ] ) ; ct1 -- ; } } res . reverse ( ) ; var ct2 = lds [ inx ] - 1 ; for ( var i = inx ; i < N && ct2 > 0 ; i ++ ) { if ( lds [ i ] == ct2 ) { res . push ( arr [ i ] ) ; ct2 -- ; } } printRes ( res ) ; } var arr = [ 80 , 60 , 30 , 40 , 20 , 10 ] ; var N = arr . length ; printLBS ( arr , N ) ;