Minimum pair merge operations required to make Array non | Function to find the minimum operations to make the array Non - increasing ; Size of the array ; Dp table initialization ; dp [ i ] : Stores minimum number of operations required to make subarray { A [ i ] , ... , A [ N ] } non - increasing ; Increment the value of j ; Add current value to sum ; Update the dp tables ; Return the answer ; Driver Code
def solve ( a ) : NEW_LINE INDENT n = len ( a ) NEW_LINE dp = [ 0 ] * ( n + 1 ) NEW_LINE val = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT sum = a [ i ] NEW_LINE j = i NEW_LINE while ( j + 1 < n and sum < val [ j + 1 ] ) : NEW_LINE INDENT j += 1 NEW_LINE sum += a [ j ] NEW_LINE DEDENT dp [ i ] = ( j - i ) + dp [ j + 1 ] NEW_LINE val [ i ] = sum NEW_LINE DEDENT return dp [ 0 ] NEW_LINE DEDENT arr = [ 1 , 5 , 3 , 9 , 1 ] NEW_LINE print ( solve ( arr ) ) NEW_LINE