Print Longest Bitonic subsequence ( Space Optimized Approach ) | Java program to implement the above 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
import java . util . * ; class GFG { static void printRes ( Vector < Integer > res ) { Enumeration enu = res . elements ( ) ; while ( enu . hasMoreElements ( ) ) { System . out . print ( enu . nextElement ( ) + " ▁ " ) ; } } static void printLBS ( int arr [ ] , int N ) { int lis [ ] = new int [ N ] ; int lds [ ] = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { lis [ i ] = lds [ i ] = 1 ; } for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( arr [ j ] < arr [ i ] ) { if ( lis [ i ] < lis [ j ] + 1 ) lis [ i ] = lis [ j ] + 1 ; } } } for ( int i = N - 1 ; i >= 0 ; i -- ) { for ( int j = N - 1 ; j > i ; j -- ) { if ( arr [ j ] < arr [ i ] ) { if ( lds [ i ] < lds [ j ] + 1 ) lds [ i ] = lds [ j ] + 1 ; } } } int MaxVal = arr [ 0 ] , inx = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( MaxVal < lis [ i ] + lds [ i ] - 1 ) { MaxVal = lis [ i ] + lds [ i ] - 1 ; inx = i ; } } int ct1 = lis [ inx ] ; Vector < Integer > res = new Vector < Integer > ( ) ; for ( int i = inx ; i >= 0 && ct1 > 0 ; i -- ) { if ( lis [ i ] == ct1 ) { res . add ( arr [ i ] ) ; ct1 -- ; } } Collections . reverse ( res ) ; int ct2 = lds [ inx ] - 1 ; for ( int i = inx ; i < N && ct2 > 0 ; i ++ ) { if ( lds [ i ] == ct2 ) { res . add ( arr [ i ] ) ; ct2 -- ; } } printRes ( res ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 80 , 60 , 30 , 40 , 20 , 10 } ; int N = arr . length ; printLBS ( arr , N ) ; } }