Remove minimum elements from either side such that 2 * min becomes more than max |  ; 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 Code
/ * A utility function to find minimum of two numbers * / NEW_LINE def min1 ( arr , l , h ) : NEW_LINE INDENT mn = arr [ l ] ; NEW_LINE for i in range ( l + 1 , h + 1 ) : NEW_LINE INDENT if ( mn > arr [ i ] ) : NEW_LINE INDENT mn = arr [ i ] ; NEW_LINE DEDENT DEDENT return mn ; NEW_LINE DEDENT def max1 ( arr , l , h ) : NEW_LINE INDENT mx = arr [ l ] ; NEW_LINE for i in range ( l + 1 , h + 1 ) : NEW_LINE INDENT if ( mx < arr [ i ] ) : NEW_LINE INDENT mx = arr [ i ] ; NEW_LINE DEDENT DEDENT return mx ; NEW_LINE DEDENT def minRemovalsDP ( arr , n ) : NEW_LINE INDENT table = [ [ 0 for x in range ( n ) ] for y in range ( n ) ] ; NEW_LINE for gap in range ( n ) : NEW_LINE INDENT i = 0 ; NEW_LINE for j in range ( gap , n ) : NEW_LINE INDENT mn = min1 ( arr , i , j ) ; NEW_LINE mx = max1 ( arr , i , j ) ; NEW_LINE table [ i ] [ j ] = 0 if ( 2 * mn > mx ) else min ( table [ i ] [ j - 1 ] + 1 , table [ i + 1 ] [ j ] + 1 ) ; NEW_LINE i += 1 ; NEW_LINE DEDENT DEDENT return table [ 0 ] [ n - 1 ] ; NEW_LINE DEDENT arr = [ 20 , 4 , 1 , 3 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( minRemovalsDP ( arr , n ) ) ; NEW_LINE