Minimum pair merge operations required to make Array non | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int solve ( vector < int > & a ) { int n = a . size ( ) ; vector < int > dp ( n + 1 , 0 ) , val ( n + 1 , 0 ) ; for ( int i = n - 1 ; i >= 0 ; i -- ) { long long sum = a [ i ] ; int j = i ; while ( j + 1 < n and sum < val [ j + 1 ] ) { j ++ ; sum += a [ j ] ; } dp [ i ] = ( j - i ) + dp [ j + 1 ] ; val [ i ] = sum ; } return dp [ 0 ] ; } int main ( ) { vector < int > arr = { 1 , 5 , 3 , 9 , 1 } ; cout << solve ( arr ) ; }