Find the minimum range
Below I try to prove that the greedy algorithm ($\mathcal{A}$) given by @norbertpy (and @Bergi) is correct. Please check it.



Problem Definition:

The algorithm $\mathcal{A}$ of @norbertpy is for a variant of the original problem:


  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' &lt; M$.

First, $m &lt; M'$: otherwise, $M'$ is a smaller feasible solution to $L[1 \cdots n-1]$, which contradicts the assumption. 

Thus we have $m &lt; M' &lt; M$. Because $M = \max(m,a)$, we obtain $m &lt; M' &lt; 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' &lt; 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.