How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?

Let $max$ denote the maximum of the sequence $a_1,…,a_n$, and let $min$ denote its minimum. If $a_1=max$, then choosing $b_1=b_2=…=b_n=lfloor(max+min)/2rfloor$ is optimal.

Why is this the case? Well, since the sequence starts with the maximum, either we choose $b_1$ large, and suffer a large deviation from the minimum of the sequence (since any subsequent $b_i$ must be greater or equal to $b_1$), or we choose $b_1$ small and suffer from the deviation to $max$. The average minimizes the maximal deviation. We can now try to generalize this observation to use on general sequences $a_1,…,a_n$. For instance, we can partition any sequence into subsequences, such that each begins with the maximum of the respective subsequence.

Example: $(2,6,4,1,5,2,8,7,5,1)$ is partitioned into $(2)$, $(6,4,1,5,2)$, and $(8,7,5,1)$.

Given this partitioning, we can now solve each these subsequences separately, and obtain an assignment of the $b_i$’s, which however might violate the non-decreasing condition. This can be fixed without losing optimality. Observe that the last subsequence always contains the maximum $max$ of the whole sequence (otherwise, there would be another subsequence after it). Let $w_1,w_2,…,w_k$ be the values we assigned to the $k$ subsequences. Now, to achieve non-decreasingness in $w_1,…,w_k$, we start from the back at $w_k$ and work our way to the front. If $w_{k-1}$ is larger than $w_k$, we simply set $w_{k-1}:=w_k$. If it is smaller, we keep it. Then, we proceed with comparing $w_{k-2}$ with $w_{k-1}$ and so on. Note that lowering any $w_i$ to the value of $w_{i+1}$ never increases the deviation, since the maximium value in the subsequence assigned with $w_i$ is always lower than the maximum in the subsequence assigned with $w_{i+1}$. This algorithm should be correct, I think. Concerning the running time, the key step is computing the increasing maxima for the subsequences, which is possible in $O(n)$? Not sure where $l$ contributes.