text: Minimum removals required to make a given array Bitonic | C ++ program to implement the above approach ; Function to coutnt minimum array elements required to be removed to make an array bitonic ; left [ i ] : Stores the length of LIS up to i - th index ; right [ i ] : Stores the length of decreasing subsequence over the range [ i , N ] ; Calculate the length of LIS up to i - th index ; Traverse the array upto i - th index ; If arr [ j ] is less than arr [ i ] ; Update left [ i ] ; Calculate the length of decreasing subsequence over the range [ i , N ] ; Traverse right [ ] array ; If arr [ i ] is greater than arr [ j ] ; Update right [ i ] ; Stores length of the longest bitonic array ; Traverse left [ ] and right [ ] array ; Update maxLen ; Function to print minimum removals required to make given array bitonic ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void min_element_removal ( int arr [ ] , int N ) { vector < int > left ( N , 1 ) ; vector < int > right ( N , 1 ) ; for ( int i = 1 ; i < N ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( arr [ j ] < arr [ i ] ) { left [ i ] = max ( left [ i ] , left [ j ] + 1 ) ; } } } for ( int i = N - 2 ; i >= 0 ; i -- ) { for ( int j = N - 1 ; j > i ; j -- ) { if ( arr [ i ] > arr [ j ] ) { right [ i ] = max ( right [ i ] , right [ j ] + 1 ) ; } } } int maxLen = 0 ; for ( int i = 1 ; i < N - 1 ; i ++ ) { maxLen = max ( maxLen , left [ i ] + right [ i ] - 1 ) ; } cout << ( N - maxLen ) << " STRNEWLINE " ; } void makeBitonic ( int arr [ ] , int N ) { if ( N == 1 ) { cout << "0" << endl ; return ; } if ( N == 2 ) { if ( arr [ 0 ] != arr [ 1 ] ) cout << "0" << endl ; else cout << "1" << endl ; return ; } min_element_removal ( arr , N ) ; } int main ( ) { int arr [ ] = { 2 , 1 , 1 , 5 , 6 , 2 , 3 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; makeBitonic ( arr , N ) ; return 0 ; }