Minimum pair merge operations required to make Array non | Java program to implement the above approach ; 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
import java . util . * ; class GFG { static int solve ( int [ ] a ) { int n = a . length ; int [ ] dp = new int [ n + 1 ] ; int [ ] val = new int [ n + 1 ] ; for ( int i = n - 1 ; i >= 0 ; i -- ) { int sum = a [ i ] ; int j = i ; while ( j + 1 < n && sum < val [ j + 1 ] ) { j ++ ; sum += a [ j ] ; } dp [ i ] = ( j - i ) + dp [ j + 1 ] ; val [ i ] = sum ; } return dp [ 0 ] ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 5 , 3 , 9 , 1 } ; System . out . print ( solve ( arr ) ) ; } }