Remove minimum elements from either side such that 2 * min becomes more than max | A O ( n * n ) solution to find the minimum of elements to be removed ; Returns the minimum number of removals from either end in arr [ l . . h ] so that 2 * min becomes greater than max . ; Initialize starting and ending indexes of the maximum sized subarray with property 2 * min > max ; Choose different elements as starting point ; Initialize min and max for the current start ; Choose different ending points for current start ; Update min and max if necessary ; If the property is violated , then no point to continue for a bigger array ; Update longest_start and longest_end if needed ; If not even a single element follow the property , then return n ; Return the number of elements to be removed ; Driver program to test above functions
class GFG { static int minRemovalsDP ( int arr [ ] , int n ) { int longest_start = - 1 , longest_end = 0 ; for ( int start = 0 ; start < n ; start ++ ) { int min = Integer . MAX_VALUE , max = Integer . MIN_VALUE ; for ( int end = start ; end < n ; end ++ ) { int val = arr [ end ] ; if ( val < min ) { min = val ; } if ( val > max ) { max = val ; } if ( 2 * min <= max ) { break ; } if ( end - start > longest_end - longest_start longest_start == - 1 ) { longest_start = start ; longest_end = end ; } } } if ( longest_start == - 1 ) { return n ; } return ( n - ( longest_end - longest_start + 1 ) ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 4 , 5 , 100 , 9 , 10 , 11 , 12 , 15 , 200 } ; int n = arr . length ; System . out . println ( minRemovalsDP ( arr , n ) ) ; } }