Minimum increment or decrement operations required to make the array sorted | 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
function getMinimumOps ( ar ) { var n = ar . length ; var small = Math . min . apply ( Math , ar ) ; var large = Math . max . apply ( Math , ar ) ; var dp = new Array ( n ) ; var i , j ; for ( i = 0 ; i < dp . length ; i ++ ) dp [ i ] = new Array ( large + 1 ) ; for ( j = small ; j <= large ; j ++ ) { dp [ 0 ] [ j ] = Math . abs ( ar [ 0 ] - j ) ; } for ( i = 1 ; i < n ; i ++ ) { var minimum = 2147483647 ; for ( j = small ; j <= large ; j ++ ) { minimum = Math . min ( minimum , dp [ i - 1 ] [ j ] ) ; dp [ i ] [ j ] = minimum + Math . abs ( ar [ i ] - j ) ; } } var ans = 2147483647 ; for ( j = small ; j <= large ; j ++ ) { ans = Math . min ( ans , dp [ n - 1 ] [ j ] ) ; } return ans ; } var ar = [ 1 , 2 , 1 , 4 , 3 ] ; document . write ( getMinimumOps ( ar ) ) ;