Minimum increment or decrement required to sort the array | Top | Python3 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 sys NEW_LINE dp = [ [ 0 for x in range ( 1000 ) ] for y in range ( 1000 ) ] NEW_LINE def minimumIncDec ( arr , N , maxE , minE ) : NEW_LINE INDENT if ( N == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ N ] [ maxE ] ) : NEW_LINE INDENT return dp [ N ] [ maxE ] NEW_LINE DEDENT ans = sys . maxsize NEW_LINE for k in range ( minE , maxE + 1 ) : NEW_LINE INDENT x = minimumIncDec ( arr , N - 1 , k , minE ) NEW_LINE ans = min ( ans , x + abs ( arr [ N - 1 ] - k ) ) NEW_LINE DEDENT dp [ N ] [ maxE ] = ans NEW_LINE return dp [ N ] [ maxE ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 5 , 4 , 3 , 2 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE minE = min ( arr ) NEW_LINE maxE = max ( arr ) NEW_LINE print ( minimumIncDec ( arr , N , maxE , minE ) ) NEW_LINE DEDENT