Minimum removals required to convert given array to a Mountain Array | Java program of the above approach ; Utility function to count array elements required to be removed to make array a mountain array ; Stores length of increasing subsequence from [ 0 , i - 1 ] ; Stores length of increasing subsequence from [ i + 1 , n - 1 ] ; Iterate for each position up to N - 1 to find the length of subsequence ; If j is less than i , then i - th position has leftIncreasing [ j ] + 1 lesser elements including itself ; Check if it is the maximum obtained so far ; Search for increasing subsequence from right ; Find the position following the peak condition and have maximum leftIncreasing [ i ] + rightIncreasing [ i ] ; Function to count elements to be removed to make array a mountain array ; Print the answer ; Driver Code ; Given array ; Function Call
import java . io . * ; import java . util . * ; class GFG { public static int minRemovalsUtil ( int [ ] arr ) { int result = 0 ; if ( arr . length < 3 ) { return - 1 ; } int [ ] leftIncreasing = new int [ arr . length ] ; int [ ] rightIncreasing = new int [ arr . length ] ; for ( int i = 1 ; i < arr . length ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( arr [ j ] < arr [ i ] ) { leftIncreasing [ i ] = Math . max ( leftIncreasing [ i ] , leftIncreasing [ j ] + 1 ) ; } } } for ( int i = arr . length - 2 ; i >= 0 ; i -- ) { for ( int j = arr . length - 1 ; j > i ; j -- ) { if ( arr [ j ] < arr [ i ] ) { rightIncreasing [ i ] = Math . max ( rightIncreasing [ i ] , rightIncreasing [ j ] + 1 ) ; } } } for ( int i = 0 ; i < arr . length ; i ++ ) { if ( leftIncreasing [ i ] != 0 && rightIncreasing [ i ] != 0 ) { result = Math . max ( result , leftIncreasing [ i ] + rightIncreasing [ i ] ) ; } } return arr . length - ( result + 1 ) ; } public static void minRemovals ( int [ ] arr ) { int ans = minRemovalsUtil ( arr ) ; System . out . println ( ans ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 2 , 1 , 1 , 5 , 6 , 2 , 3 , 1 } ; minRemovals ( arr ) ; } }