human
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"
Solution in Python:
assistant
#Here is code to printing Longest Bitonic Subsequence and the other steps required.
 def _print ( arr : list , size : int ) :
	for i in range ( size ) :
		print ( arr [ i ] , end = " ▁ " )
def printLBS ( arr : list , n : int ) :
	LIS = [ 0 ] * n
	for i in range ( n ) :
		LIS [ i ] = [ ]
	LIS [ 0 ] . append ( arr [ 0 ] )
	for i in range ( 1 , n ) :
		for j in range ( i ) :
			if ( ( arr [ j ] < arr [ i ] ) and ( len ( LIS [ j ] ) > len ( LIS [ i ] ) ) ) :
				LIS [ i ] = LIS [ j ] . copy ( )
		LIS [ i ] . append ( arr [ i ] )
	LDS = [ 0 ] * n
	for i in range ( n ) :
		LDS [ i ] = [ ]
	LDS [ n - 1 ] . append ( arr [ n - 1 ] )
	for i in range ( n - 2 , - 1 , - 1 ) :
		for j in range ( n - 1 , i , - 1 ) :
			if ( ( arr [ j ] < arr [ i ] ) and ( len ( LDS [ j ] ) > len ( LDS [ i ] ) ) ) :
				LDS [ i ] = LDS [ j ] . copy ( )
		LDS [ i ] . append ( arr [ i ] )
	for i in range ( n ) :
		LDS [ i ] = list ( reversed ( LDS [ i ] ) )
	max = 0
	maxIndex = - 1
	for i in range ( n ) :
		if ( len ( LIS [ i ] ) + len ( LDS [ i ] ) - 1 > max ) :
			max = len ( LIS [ i ] ) + len ( LDS [ i ] ) - 1
			maxIndex = i
	_print ( LIS [ maxIndex ] , len ( LIS [ maxIndex ] ) - 1 )
	_print ( LDS [ maxIndex ] , len ( LDS [ maxIndex ] ) )
if __name__ == " _ _ main _ _ " :
	arr = [ 1 , 11 , 2 , 10 , 4 , 5 , 2 , 1 ]
	n = len ( arr )
	printLBS ( arr , n )