Remove minimum elements from either side such that 2 * min becomes more than max | Java program of above approach ; A utility function to find minimum of two numbers ; A utility function to find minimum in arr [ l . . h ] ; A utility function to find maximum in arr [ l . . h ] ; Returns the minimum number of removals from either end in arr [ l . . h ] so that 2 * min becomes greater than max . ; Create a table to store solutions of subproblems ; Fill table using above recursive formula . Note that the table is filled in diagonal fashion ( similar to http : goo . gl / PQqoS ) , from diagonal elements to table [ 0 ] [ n - 1 ] which is the result . ; Driver program to test above functions
class GFG { static int min ( int a , int b ) { return ( a < b ) ? a : b ; } static int min ( int arr [ ] , int l , int h ) { int mn = arr [ l ] ; for ( int i = l + 1 ; i <= h ; i ++ ) { if ( mn > arr [ i ] ) { mn = arr [ i ] ; } } return mn ; } static int max ( int arr [ ] , int l , int h ) { int mx = arr [ l ] ; for ( int i = l + 1 ; i <= h ; i ++ ) { if ( mx < arr [ i ] ) { mx = arr [ i ] ; } } return mx ; } static int minRemovalsDP ( int arr [ ] , int n ) { int table [ ] [ ] = new int [ n ] [ n ] , gap , i , j , mn , mx ; for ( gap = 0 ; gap < n ; ++ gap ) { for ( i = 0 , j = gap ; j < n ; ++ i , ++ j ) { mn = min ( arr , i , j ) ; mx = max ( arr , i , j ) ; table [ i ] [ j ] = ( 2 * mn > mx ) ? 0 : min ( table [ i ] [ j - 1 ] + 1 , table [ i + 1 ] [ j ] + 1 ) ; } } return table [ 0 ] [ n - 1 ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 20 , 4 , 1 , 3 } ; int n = arr . length ; System . out . println ( minRemovalsDP ( arr , n ) ) ; } }