[Solved]: Find the minimum range

To find the minimum positive number $2m$ such that for each item in the array, adding a number from $[0, 2m]$ can lead to a strictly ascending array?

The solutions to these two problems can be reduced to each other (by $pm m$). Note that I have ignored the “except the last” part. A lemma for the property of the algorithm $mathcal{A}$: Let $L'[n]$ be the last element of the resulting strictly ascending list of any feasible solution to $L[1 ldots n]$. We first claim that:

Lemma: $mathcal{A}$ gives the smallest value of $L'[n]$ among all the feasible solutions to $L[1 ldots n]$.

This lemma can be proved by mathematical induction on the length $n$ of $L$. Now we prove that $mathcal{A}$ always gives the optimal solution. Base case: $n = 1$ and $n = 2$ are trivial. Inductive Hypothesis: Suppose that for any $L[1 cdots n-1]$ of length $n-1$, the algorithm $mathcal{A}$ gives us the optimal solution $m$. Inductive Step: Consider the $n$-th iteration of the greedy algorithm $mathcal{A}$: it compare a = head + 1 – L[n] with $m$, and take $M = max(m,a)$ as the feasible solution to $L[1 cdots n]$. We aim to prove that

$M$ is the optimal solution to $L[1 cdots n]$.

Suppose, by contradiction, that there is another feasible solution to $L[1 cdots n]$, denoted by $M’ < M$. First, $m < M’$: otherwise, $M’$ is a smaller feasible solution to $L[1 cdots n-1]$, which contradicts the assumption. Thus we have $m < M’ < M$. Because $M = max(m,a)$, we obtain $m < M’ < M = a$. By the lemma above, $L'[n-1]$ in the solution corresponding to $M’$ is not less than that in the solution corresponding to $m$. However, $L'[n]$ (for $M’$) is less than that for $M$ (because $M’ < a$). According to the way how $a$ is chosen in $mathcal{A}$, the resulting array (for $M’$) is not strictly ascending. Thus $M’$ cannot be a solution. Contradication.