Minimum increment or decrement required to sort the array | Top | C # program of the above approach ; Dp array to memoized the value recursive call ; Function to find the minimum increment or decrement needed to make the array sorted ; If only one element is present , then [ ] arr is sorted ; If dp [ N , maxE ] is precalculated , then return the result ; Iterate from minE to maxE which placed at previous index ; Update the answer according to recurrence relation ; Memoized the value for dp [ N , maxE ] ; Return the readonly result ; Driver Code ; Find the minimum and maximum element from the [ ] arr ; Function call
using System ; using System . Linq ; class GFG { static int [ , ] dp = new int [ 1000 , 1000 ] ; static int minimumIncDec ( int [ ] arr , int N , int maxE , int minE ) { if ( N == 0 ) { return 0 ; } if ( dp [ N , maxE ] != 0 ) return dp [ N , maxE ] ; int ans = int . MaxValue ; for ( int k = minE ; k <= maxE ; k ++ ) { int x = minimumIncDec ( arr , N - 1 , k , minE ) ; ans = Math . Min ( ans , x + Math . Abs ( arr [ N - 1 ] - k ) ) ; } dp [ N , maxE ] = ans ; return dp [ N , maxE ] ; } public static void Main ( String [ ] args ) { int [ ] arr = { 5 , 4 , 3 , 2 , 1 } ; int N = arr . Length ; int minE = arr . Min ( ) ; int maxE = arr . Max ( ) ; Console . Write ( minimumIncDec ( arr , N , maxE , minE ) ) ; } }