Minimum increment or decrement required to sort the array | Top | 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 final result ; Driver Code ; Find the minimum and maximum element from the arr [ ] ; Function Call
let dp = new Array ( ) ; for ( let i = 0 ; i < 1000 ; i ++ ) { let temp = [ ] ; for ( let j = 0 ; j < 1000 ; j ++ ) { temp . push ( [ ] ) } dp . push ( temp ) } function minimumIncDec ( arr , N , maxE , minE ) { if ( N == 0 ) { return 0 ; } if ( ! dp [ N ] [ maxE ] ) return dp [ N ] [ maxE ] ; let ans = Number . MAX_SAFE_INTEGER ; for ( let k = minE ; k <= maxE ; k ++ ) { let 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 ] ; } let arr = [ 5 , 4 , 3 , 2 , 1 ] ; let N = arr . length ; let minE = arr . sort ( ( a , b ) => a - b ) [ 0 ] ; let maxE = arr . sort ( ( a , b ) => b - a ) [ 0 ] ; document . write ( minimumIncDec ( arr , N , maxE , minE ) ) ;