Minimum increment or decrement operations required to make the array sorted | C ++ implementation of the approach ; Function to return the minimum number of given operations required to sort the array ; Number of elements in the array ; Smallest element in the array ; Largest element in the array ; dp ( i , j ) represents the minimum number of operations needed to make the array [ 0 . . i ] sorted in non - decreasing order given that ith element is j ; Fill the dp [ ] ] [ array for base cases ; Using results for the first ( i - 1 ) elements , calculate the result for the ith element ; If the ith element is j then we can have any value from small to j for the i - 1 th element We choose the one that requires the minimum operations ; If we made the ( n - 1 ) th element equal to j we required dp ( n - 1 , j ) operations We choose the minimum among all possible dp ( n - 1 , j ) where j goes from small to large ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getMinimumOps ( vector < int > ar ) { int n = ar . size ( ) ; int small = * min_element ( ar . begin ( ) , ar . end ( ) ) ; int large = * max_element ( ar . begin ( ) , ar . end ( ) ) ; int dp [ n ] [ large + 1 ] ; for ( int j = small ; j <= large ; j ++ ) { dp [ 0 ] [ j ] = abs ( ar [ 0 ] - j ) ; } for ( int i = 1 ; i < n ; i ++ ) { int minimum = INT_MAX ; for ( int j = small ; j <= large ; j ++ ) { minimum = min ( minimum , dp [ i - 1 ] [ j ] ) ; dp [ i ] [ j ] = minimum + abs ( ar [ i ] - j ) ; } } int ans = INT_MAX ; for ( int j = small ; j <= large ; j ++ ) { ans = min ( ans , dp [ n - 1 ] [ j ] ) ; } return ans ; } int main ( ) { vector < int > ar = { 1 , 2 , 1 , 4 , 3 } ; cout << getMinimumOps ( ar ) ; return 0 ; }