Longest Reverse Bitonic Sequence | C ++ program to find the longest Reverse bitonic Subsequence ; Function to return the length of the Longest Reverse Bitonic Subsequence in the array ; Allocate memory for LIS [ ] and initialize LIS values as 1 for all indexes ; Compute LIS values from left to right for every index ; Initialize LDS for all indexes as 1 ; Compute LDS values for every index from right to left ; Find the maximum value of lis [ i ] + lds [ i ] - 1 in the array ; Return the maximum ; Driver Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int ReverseBitonic ( int arr [ ] , int N ) { int i , j ; int lds [ N ] ; for ( i = 0 ; i < N ; i ++ ) { lds [ i ] = 1 ; } for ( i = 1 ; i < N ; i ++ ) { for ( j = 0 ; j < i ; j ++ ) { if ( arr [ i ] < arr [ j ] && lds [ i ] < lds [ j ] + 1 ) { lds [ i ] = lds [ j ] + 1 ; } } } int lis [ N ] ; for ( i = 0 ; i < N ; i ++ ) { lis [ i ] = 1 ; } for ( i = N - 2 ; i >= 0 ; i -- ) { for ( j = N - 1 ; j > i ; j -- ) { if ( arr [ i ] < arr [ j ] && lis [ i ] < lis [ j ] + 1 ) { lis [ i ] = lis [ j ] + 1 ; } } } int max = lis [ 0 ] + lds [ 0 ] - 1 ; for ( i = 1 ; i < N ; i ++ ) { if ( lis [ i ] + lds [ i ] - 1 > max ) { max = lis [ i ] + lds [ i ] - 1 ; } } return max ; } int main ( ) { int arr [ ] = { 0 , 8 , 4 , 12 , 2 , 10 , 6 , 14 , 1 , 9 , 5 , 13 , 3 , 11 , 7 , 15 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printf ( " Length ▁ of ▁ LBS ▁ is ▁ % d STRNEWLINE " , ReverseBitonic ( arr , N ) ) ; return 0 ; }