Printing Longest Bitonic Subsequence | Dynamic Programming solution to print 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
import java . util . * ; class GFG { static void print ( Vector < Integer > arr , int size ) { for ( int i = 0 ; i < size ; i ++ ) System . out . print ( arr . elementAt ( i ) + " ▁ " ) ; } static void printLBS ( int [ ] arr , int n ) { @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] LIS = new Vector [ n ] ; for ( int i = 0 ; i < n ; i ++ ) LIS [ i ] = new Vector < > ( ) ; LIS [ 0 ] . add ( arr [ 0 ] ) ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( ( arr [ i ] > arr [ j ] ) && LIS [ j ] . size ( ) > LIS [ i ] . size ( ) ) { for ( int k : LIS [ j ] ) if ( ! LIS [ i ] . contains ( k ) ) LIS [ i ] . add ( k ) ; } } LIS [ i ] . add ( arr [ i ] ) ; } @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] LDS = new Vector [ n ] ; for ( int i = 0 ; i < n ; i ++ ) LDS [ i ] = new Vector < > ( ) ; LDS [ n - 1 ] . add ( arr [ n - 1 ] ) ; for ( int i = n - 2 ; i >= 0 ; i -- ) { for ( int j = n - 1 ; j > i ; j -- ) { if ( arr [ j ] < arr [ i ] && LDS [ j ] . size ( ) > LDS [ i ] . size ( ) ) for ( int k : LDS [ j ] ) if ( ! LDS [ i ] . contains ( k ) ) LDS [ i ] . add ( k ) ; } LDS [ i ] . add ( arr [ i ] ) ; } for ( int i = 0 ; i < n ; i ++ ) Collections . reverse ( LDS [ i ] ) ; int max = 0 ; int maxIndex = - 1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( LIS [ i ] . size ( ) + LDS [ i ] . size ( ) - 1 > max ) { max = LIS [ i ] . size ( ) + LDS [ i ] . size ( ) - 1 ; maxIndex = i ; } } print ( LIS [ maxIndex ] , LIS [ maxIndex ] . size ( ) - 1 ) ; print ( LDS [ maxIndex ] , LDS [ maxIndex ] . size ( ) ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 11 , 2 , 10 , 4 , 5 , 2 , 1 } ; int n = arr . length ; printLBS ( arr , n ) ; } }