Minimum removals required to make a given array Bitonic | Java 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
class GFG { static void min_element_removal ( int arr [ ] , int N ) { int left [ ] = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) left [ i ] = 1 ; int right [ ] = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) right [ i ] = 1 ; for ( int i = 1 ; i < N ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( arr [ j ] < arr [ i ] ) { left [ i ] = Math . 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 ] = Math . max ( right [ i ] , right [ j ] + 1 ) ; } } } int maxLen = 0 ; for ( int i = 1 ; i < N - 1 ; i ++ ) { maxLen = Math . max ( maxLen , left [ i ] + right [ i ] - 1 ) ; } System . out . println ( N - maxLen ) ; } static void makeBitonic ( int arr [ ] , int N ) { if ( N == 1 ) { System . out . println ( "0" ) ; return ; } if ( N == 2 ) { if ( arr [ 0 ] != arr [ 1 ] ) System . out . println ( "0" ) ; else System . out . println ( "1" ) ; return ; } min_element_removal ( arr , N ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 1 , 1 , 5 , 6 , 2 , 3 , 1 } ; int N = arr . length ; makeBitonic ( arr , N ) ; } }