Given a sequence *A* of *n* integers, design an algorithm to find an non-decreasing sequence *B* of *n* integers, such that is minimized.

**Solution**:

This problem can be solved by minimum cost flow. Here we use dynamic programming.

Let *F*(*k*, *z*) be the optimal objective value for the first *k* elements with *B*[*k*] = *z*. Then, we have a recurrence relation: *F*(*k*, *z*) = min *F*(*k*-1, *x*) + |*z* – *A*[*k*]|. Thus, the problem becomes how to efficiently find the *z* minimizing *F*(*k*, *z*) for all fixed *k*. It can be showed that *F*(*k*, *z*) is a piecewise linear convex function in *z* and the minimizing value must be in *A*. Thus, the dynamic programming can be speed up by using slope optimization and find the solution in O(*n* lg *n*) time.

**解法**：

令 *F*(*k*, *z*) 為前 *k* 個元素且 *B*[*k*] = *z *時的最佳解之值。當給定 *k* ，我們可得一遞回關係式：*F*(*k*, *z*) = min *F*(*k*-1, *x*) + |*z* – *A*[*k*]|。因此問題就變成如何快速的找出最小化 *F*(*k*, *z*) 的 *z* 值。我們可以證明 *F*(*k*, *z*) 對於 *z* 是一個 piecewise linear convex 函數 ，而且可以最小化 *F *的 *z* 值必定在 A 中。因此使用動態規劃加上斜率最佳化可以在O(*n* lg *n*)時間內找到答案。

Reference: Stackoverflow, Stackoverflow

Günter Rote, “Isotonic Regression by Dynamic Programming”