Sequence

Forget the literal $+1/-1$ operations. They are just a dramatic way to say this:

choose integers $b_1, b_2, \dots, b_n$ such that $b_1 \le b_2 \le \dots \le b_n$ and minimize $\sum_{i=1}^n |a_i-b_i|.$

So this is an $L_1$ isotonic regression problem. Sounds fancy. The solution is just a clean DP once you stop the problem from cosplaying as a simulation.

Observation 1: only original values matter

Let $V$ be the set of distinct values appearing in the original array. We claim there exists an optimal answer where every $b_i$ belongs to $V$.

Why? Take any optimal non-decreasing sequence $b$, and suppose some value $x \notin V$ appears. Look at one maximal block $b_l = b_{l+1} = \dots = b_r = x.$ Let $L = b_{l-1} \text{ (or } -\infty\text{)}, \qquad R = b_{r+1} \text{ (or } +\infty\text{)}.$ To keep the sequence non-decreasing, we may replace the whole block by any value $t$ with $L \le t \le R$.

Now let $p < x < q$ be consecutive values in $V \cup \{-\infty, +\infty\}$ around $x$. Since no original value lies inside $(p,q)$, the block cost $f(t) = \sum_{i=l}^r |a_i-t|$ is linear on $(p,q)$. Therefore on the feasible interval $[L,R] \cap [p,q]$ it reaches its minimum at an endpoint.

That endpoint is either:

• $p$ or $q$, which is an original value, or
• $L$ or $R$, which merges this block with a neighboring block.

In both cases we do not increase the cost, and we reduce the number of weird target values not from $V$. Repeat this until all chosen values are from $V$.

So we only need to consider candidate target values from the sorted original array. You can keep duplicates or remove them; both work. I will use the distinct sorted values $c_1 < c_2 < \dots < c_m$.

Observation 2: DP on position and chosen value

Define $dp[i][j] = \text{minimum cost for the first } i \text{ elements if } b_i = c_j.$

If $b_i = c_j$, then because $b$ must be non-decreasing, the previous value $b_{i-1}$ must be some $c_k$ with $k \le j$. Therefore $dp[i][j] = |a_i-c_j| + \min_{k \le j} dp[i-1][k].$

That is the whole problem. No black magic, just one honest transition.

Observation 3: kill the inner minimum with prefix minima

Naively, the transition is $O(m)$ per state, which would be $O(nm^2)$ and kind of gross.

But for fixed $i$, the needed value is just a prefix minimum: $pref[j] = \min(pref[j-1], dp[i-1][j]).$ Then $dp[i][j] = |a_i-c_j| + pref[j].$

So each DP row can be computed in one left-to-right pass.

We can initialize $dp[0][j] = 0$ for all $j$, meaning before processing any elements, the cost is zero regardless of the last chosen candidate. After processing all $n$ elements, the answer is $\min_j dp[n][j].$

Complexity

Let $m$ be the number of distinct values in the array. Then:

• Time: $O(nm) \le O(n^2)$
• Memory: $O(m)$ using two rows

With $n \le 5000$, this passes comfortably.

Tiny implementation notes

• Use long long. The answer can be around $5000 \cdot 2\cdot 10^9$, which absolutely does not fit in int.
• Removing duplicates from the sorted candidate list is optional. It just saves a few states.

That is it. Once you rephrase the cost correctly, the problem stops being scary and becomes a very standard monotone DP.