Minimum increment or decrement required to sort the array | Top | Java 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 final result ; Driver Code ; Find the minimum and maximum element from the arr [ ] ; Function call
import java . util . * ; 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 = Integer . MAX_VALUE ; 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 = Arrays . stream ( arr ) . min ( ) . getAsInt ( ) ; int maxE = Arrays . stream ( arr ) . max ( ) . getAsInt ( ) ; System . out . print ( minimumIncDec ( arr , N , maxE , minE ) ) ; } }