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 Code
import sys ; NEW_LINE def minRemovalsDP ( arr , n ) : NEW_LINE INDENT longest_start = - 1 ; NEW_LINE longest_end = 0 ; NEW_LINE for start in range ( n ) : NEW_LINE INDENT min = sys . maxsize ; NEW_LINE max = - sys . maxsize ; NEW_LINE for end in range ( start , n ) : NEW_LINE INDENT val = arr [ end ] ; NEW_LINE if ( val < min ) : NEW_LINE INDENT min = val ; NEW_LINE DEDENT if ( val > max ) : NEW_LINE INDENT max = val ; NEW_LINE DEDENT if ( 2 * min <= max ) : NEW_LINE INDENT break ; NEW_LINE DEDENT if ( end - start > longest_end - longest_start or longest_start == - 1 ) : NEW_LINE INDENT longest_start = start ; NEW_LINE longest_end = end ; NEW_LINE DEDENT DEDENT DEDENT if ( longest_start == - 1 ) : NEW_LINE INDENT return n ; NEW_LINE DEDENT return ( n - ( longest_end - longest_start + 1 ) ) ; NEW_LINE DEDENT arr = [ 4 , 5 , 100 , 9 , 10 , 11 , 12 , 15 , 200 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( minRemovalsDP ( arr , n ) ) ; NEW_LINE