Complexity of an edit distance problem Given an array $A[1...n]$ of non-negative integers, 
we want to transform $A$ into $A'$ such that

$|A[I] - A[I + 1]| \leq 1$ in the minimum number of operations. 

One operation consist of picking two adjacent elements and perform:

1) Add 1 to $A[I]$ and subtract 1 from $A[I + 1]$

2) Subtract 1 from $A[I]$ and Add 1 to $A[I + 1]$

E.g.: 1 3 5 2
1 4 4 2 (picking 3,5)
2 3 4 2 (picking 1,4)
2 3 3 3 (picking 4,2)
I give a rough idea to solve the problem in polynomial time.


In the optimal solution, the flow on each edge is unidirectional.
The final value of each element is not far from the mean. Also $\sum_{i&lt;k}A'_i$, the prefix-sum of the optimal $A'$, is bounded in a range at most $O(n^2)$.
Let $T(k,R)$ be the optimal flow on the first $k$ edges such that $\sum_{i&lt;k}A'_i=R$. Then $T(k,R)$ can be computed from $T(k-1,R')$ for all possible $R'$. 


These imply a dynamic programming algorithm with polynomial time complexity.