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 program
#include <bits/stdc++.h> NEW_LINE using namespace std ; void print ( vector < int > & arr , int size ) { for ( int i = 0 ; i < size ; i ++ ) cout << arr [ i ] << " ▁ " ; } void printLBS ( int arr [ ] , int n ) { vector < vector < int > > LIS ( n ) ; LIS [ 0 ] . push_back ( arr [ 0 ] ) ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( ( arr [ j ] < arr [ i ] ) && ( LIS [ j ] . size ( ) > LIS [ i ] . size ( ) ) ) LIS [ i ] = LIS [ j ] ; } LIS [ i ] . push_back ( arr [ i ] ) ; } vector < vector < int > > LDS ( n ) ; LDS [ n - 1 ] . push_back ( 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 ( ) ) ) LDS [ i ] = LDS [ j ] ; } LDS [ i ] . push_back ( arr [ i ] ) ; } for ( int i = 0 ; i < n ; i ++ ) reverse ( LDS [ i ] . begin ( ) , LDS [ i ] . end ( ) ) ; 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 ( ) ) ; } int main ( ) { int arr [ ] = { 1 , 11 , 2 , 10 , 4 , 5 , 2 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printLBS ( arr , n ) ; return 0 ; }