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
using System ; using System . Linq ; using System . Collections . Generic ; class GFG { static int getMinimumOps ( List < int > ar ) { int n = ar . Count ; int small = ar . Min ( ) ; int large = ar . Max ( ) ; int [ , ] dp = new int [ n , large + 1 ] ; for ( int j = small ; j <= large ; j ++ ) { dp [ 0 , j ] = Math . Abs ( ar [ 0 ] - j ) ; } for ( int i = 1 ; i < n ; i ++ ) { int minimum = int . MaxValue ; for ( int j = small ; j <= large ; j ++ ) { minimum = Math . Min ( minimum , dp [ i - 1 , j ] ) ; dp [ i , j ] = minimum + Math . Abs ( ar [ i ] - j ) ; } } int ans = int . MaxValue ; for ( int j = small ; j <= large ; j ++ ) { ans = Math . Min ( ans , dp [ n - 1 , j ] ) ; } return ans ; } public static void Main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 1 , 4 , 3 } ; List < int > ar = new List < int > ( arr ) ; Console . WriteLine ( getMinimumOps ( ar ) ) ; } }