Printing Longest Bitonic Subsequence | Utility function to print Longest Bitonic Subsequence ; Function to construct and print Longest Bitonic Subsequence ; LIS [ i ] stores the length of the longest increasing subsequence ending with arr [ i ] ; initialize LIS [ 0 ] to arr [ 0 ] ; Compute LIS values from left to right ; for every j less than i ; LDS [ i ] stores the length of the longest decreasing subsequence starting with arr [ i ] ; initialize LDS [ n - 1 ] to arr [ n - 1 ] ; Compute LDS values from right to left ; for every j greater than i ; reverse as vector as we 're inserting at end ; LDS [ i ] now stores Maximum Decreasing Subsequence of arr [ i . . n ] that starts with arr [ i ] ; Find maximum value of size of LIS [ i ] + size of LDS [ i ] - 1 ; print all but last element of LIS [ maxIndex ] vector ; print all elements of LDS [ maxIndex ] vector ; Driver Code
def _print ( arr : list , size : int ) : NEW_LINE INDENT for i in range ( size ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT def printLBS ( arr : list , n : int ) : NEW_LINE INDENT LIS = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT LIS [ i ] = [ ] NEW_LINE DEDENT LIS [ 0 ] . append ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if ( ( arr [ j ] < arr [ i ] ) and ( len ( LIS [ j ] ) > len ( LIS [ i ] ) ) ) : NEW_LINE INDENT LIS [ i ] = LIS [ j ] . copy ( ) NEW_LINE DEDENT DEDENT LIS [ i ] . append ( arr [ i ] ) NEW_LINE DEDENT LDS = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT LDS [ i ] = [ ] NEW_LINE DEDENT LDS [ n - 1 ] . append ( arr [ n - 1 ] ) NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( n - 1 , i , - 1 ) : NEW_LINE INDENT if ( ( arr [ j ] < arr [ i ] ) and ( len ( LDS [ j ] ) > len ( LDS [ i ] ) ) ) : NEW_LINE INDENT LDS [ i ] = LDS [ j ] . copy ( ) NEW_LINE DEDENT DEDENT LDS [ i ] . append ( arr [ i ] ) NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT LDS [ i ] = list ( reversed ( LDS [ i ] ) ) NEW_LINE DEDENT max = 0 NEW_LINE maxIndex = - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( len ( LIS [ i ] ) + len ( LDS [ i ] ) - 1 > max ) : NEW_LINE INDENT max = len ( LIS [ i ] ) + len ( LDS [ i ] ) - 1 NEW_LINE maxIndex = i NEW_LINE DEDENT DEDENT _print ( LIS [ maxIndex ] , len ( LIS [ maxIndex ] ) - 1 ) NEW_LINE _print ( LDS [ maxIndex ] , len ( LDS [ maxIndex ] ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 11 , 2 , 10 , 4 , 5 , 2 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE printLBS ( arr , n ) NEW_LINE DEDENT