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
def printRes ( res ) : NEW_LINE INDENT n = len ( res ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( res [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT def printLBS ( arr , N ) : NEW_LINE INDENT lis = [ 0 ] * N NEW_LINE lds = [ 0 ] * N NEW_LINE for i in range ( N ) : NEW_LINE INDENT lis [ i ] = lds [ i ] = 1 NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if arr [ j ] < arr [ i ] : NEW_LINE INDENT if lis [ i ] < lis [ j ] + 1 : NEW_LINE INDENT lis [ i ] = lis [ j ] + 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( N - 1 , i , - 1 ) : NEW_LINE INDENT if arr [ j ] < arr [ i ] : NEW_LINE INDENT if lds [ i ] < lds [ j ] + 1 : NEW_LINE INDENT lds [ i ] = lds [ j ] + 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT MaxVal = arr [ 0 ] NEW_LINE inx = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if MaxVal < lis [ i ] + lds [ i ] - 1 : NEW_LINE INDENT MaxVal = lis [ i ] + lds [ i ] - 1 NEW_LINE inx = i NEW_LINE DEDENT DEDENT ct1 = lis [ inx ] NEW_LINE res = [ ] NEW_LINE i = inx NEW_LINE while i >= 0 and ct1 > 0 : NEW_LINE INDENT if lis [ i ] == ct1 : NEW_LINE INDENT res . append ( arr [ i ] ) NEW_LINE ct1 -= 1 NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT res . reverse ( ) NEW_LINE ct2 = lds [ inx ] - 1 NEW_LINE i = inx NEW_LINE while i < N and ct2 > 0 : NEW_LINE INDENT if lds [ i ] == ct2 : NEW_LINE INDENT res . append ( arr [ i ] ) NEW_LINE ct2 -= 1 NEW_LINE DEDENT i += 1 NEW_LINE DEDENT printRes ( res ) NEW_LINE DEDENT arr = [ 80 , 60 , 30 , 40 , 20 , 10 ] NEW_LINE N = len ( arr ) NEW_LINE printLBS ( arr , N ) NEW_LINE