# Determine Minimal Adjustment Cost of an Array

Write an algorithm to replace each element in an array of positive integers such that the difference between adjacent elements in the array is less than or equal to a given target. We need to minimize the adjustment cost which is the sum of differences between new and old values.

In other words, minimize `∑|A[i] – Anew[i]|`, where `0 <= i <= n-1`, n is size of `A[]` and `Anew[]` is the array with adjacent difference less that or equal to target.

For example,

Input: arr = [1, 3, 0, 3], target = 1
Output: Minimum adjustment cost is 3

One of the possible solutions is [2, 3, 2, 3]

Input: arr = [55, 77, 52, 61, 39, 6, 25, 60, 49, 47], target = 10
Output: Minimum adjustment cost is 75

One of the possible solutions is [55, 62, 52, 49, 39, 29, 30, 40, 49, 47]

Input: arr = [2, 3, 2, 3], target = 1
Output: Minimum adjustment cost is 0
All adjacent elements in the input array are already less than equal to given target

In order to minimize the adjustment cost `∑|A[i] – Anew[i]|` for all index `i` in the array,
`|A[i] – Anew[i]|` should be as close to 0 as possible. Also, `|A[i] – Anew[i+1] ]| <= Target`.

We can use Dynamic Programming to solve this problem. Let `T[i][j]` defines minimal adjustment cost on changing `A[i]` to `j`, then the DP relation is defined by –

`T[i][j] = min{T[i - 1][k]} + |j - A[i]|`     for all k's such that `|k - j| <= target`

Here, `0 <= i < n` and `0 <= j <= M` where n is number of elements in the array. We have to consider all `k` such that `max(j – target, 0) <= k <= min(M, j + target)`. Finally the minimum adjustment cost of the array will be `min{T[n – 1][j]}` for all `0 <= j <= M`.

## C

Output:

The minimal adjustment cost is 75

## Java

Output:

The minimal adjustment cost is 75

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding :)

Get great deals at Amazon