Transforming an array into one with descending order
There is an efficient dynamic programming solution if the input domain is small.

Let $C_i(v)$ be the cost of increasing/reducing elements such that $\hat a_i = v \wedge (\forall j &gt;i)[\hat a_{j} \leq v]$.

It should be obvious that $C_n(v)$ is simply $|a_n - v|$, and thus computing $C_n$ completely is easy.

Then $C_{i}(v)$ is $|a_i - v| + \min(C_{i+1}(0), C_{i+1}(1),\dots,C_{i+1}(v))$. Using this we can compute $C$ as a table, using $C_{i+1}$ to fill $C_i$, working backwards all the way to $C_1$. Then choosing the minimal element of $C_1$ and working forwards again you have found the solution.