Remove minimum elements from either side such that 2 * min becomes more than max | 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
< ? php function minRemovalsDP ( $ arr , $ n ) { $ longest_start = -1 ; $ longest_end = 0 ; for ( $ start = 0 ; $ start < $ n ; $ start ++ ) { $ min = PHP_INT_MAX ; $ max = PHP_INT_MIN ; for ( $ end = $ start ; $ end < $ n ; $ end ++ ) { $ 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 ) ) ; } $ arr = array ( 4 , 5 , 100 , 9 , 10 , 11 , 12 , 15 , 200 ) ; $ n = sizeof ( $ arr ) ; echo minRemovalsDP ( $ arr , $ n ) ; ? >