Transforming an array into one with descending order

Problem Description

Given an array $A$ of $n$ integers, find the minimum number of operations to turn it into a new array $\widehat{A}$ with a (weakly) descending order: we require that $\hat{a}_i \geq \hat{a}_j$ for all $1\leq i

-
If not, what algorithm solves this problem with the best time complexity?

My efforts

We can write this problem as an integer linear programming. Say the elements in the array are $a_1,a_2,\ldots,a_n$, and those in the new array are $\hat{a}_1,\ldots,\hat{a}_n$ then the problem is essentially an interger programming:

$$
\begin{align*}
\text{minimize}\quad &\left|\hat{a}_1-a_1\right|+\cdots+\left|\hat{a}_n-a_n\right| \\
\text{subject to}\quad &\hat{a}_1\ge\cdots\ge\hat{a}_n
\end{align*}
$$

or equivalentlly

$$
\begin{align*}
\text{minimize}\quad &t_1+\cdots+t_n \\
\text{subject to}\quad &\hat{a}_i-a_i\le t_i, &i=1,\ldots,n\\
&-\left(\hat{a}_i-a_i\right)\le t_i, &i=1,\ldots,n\\
&\hat{a}_1\ge\cdots\ge\hat{a}_n
\end{align*}
$$

But it seems not to help because the coefficient matrix is not totally unimodular, thus we cannot relax it to linear programming.

I also find a property of optimum solutions:


If some consecutive elements are originally in non-descending order, then they must be the same in an optimum solution.

I don't know whether this property helps.

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 >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.

StackExchange Computer Science Q#87132, answer score: 3