Find the minimum range

Given a list of numbers as L, how do you find the minimum value m such that L can be made into a strictly ascending list by adding or subtracting values from [0,m] from each element of L except the last? (Strictly ascending means the new list can't have any duplicates.)

Example #1:

for L = [5, 4, 3, 2, 8] the minimum value for m is 3.
5 - 3 = 2 # subtract by 3
4 - 1 = 3 # subtract by 1
3 + 1 = 4 # add by 1
2 + 3 = 5 # add by 3
8 untouched # nothing

result = [2, 3, 4, 5, 8]

Example #2:

for L = [5, 4, 3, 0, 8], minimum value for m is 4

NOTE: I'm not looking for a complete solution just give me few thoughts and clue.

• Try first solving the problem for very short $L$, say of sizes $2,3,4$. Then come up with a formula. Then come up with an efficient algorithm for computing it. – Yuval Filmus Apr 17 '15 at 4:19
• Maybe try dynamic programming. Do you have more examples for checking? – hengxin Apr 17 '15 at 10:00
• @YuvalFilmus, @hengnix. Thanks. I know it must be solved by DP and some kind of backtracking but I'm unable to find a good way to solve it even for a short list. Let's say, I pick the min of the list (here 2) and then iterate over the list and try to find the minimum value m that either item + m or item - m is still greater than min . Now, next item and updated min and so on. But that doesn't take me any where. – norbertpy Apr 17 '15 at 16:39
• @hengxin, I'll try to find some more examples. That's gonna help. There are few solutions that I'm not sure if correct or not. But I don't understand their logic. Here, here and here – norbertpy Apr 17 '15 at 16:49

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' < 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.

Inspired by Bergi's answer, I've written this:

import math

a = [5, 4, 3, 2, 8]
b = [5, 4, 3, 0, 8]
c = [5, 4, 110, 0, 8]
d = [5, 4, 3, -16, 8]

def hill(a):
max_m = 0
for item in a[1:]:
current_m = math.fabs(head + 1 - item)

if current_m > max_m:
max_m = current_m

# update the head for next iteration
head = item + current_m

print math.ceil(max_m / 2)

hill(a) # 3.0
hill(b) # 4.0
hill(c) # 107.0
hill(d) # 12.0

The logic is, we set the max_m to zero and the head to first element of the list. We then start iterating through the list - first element and find the minimum value current_m such that adding current_m to the item will be equal to head + 1. At each iteration of we find a greater m, we just store it in max_m.

At the end we divide the m by 2 since we just used the addition to find the m and not the subtraction.

I hope this helps but I'm still not sure if it's correct for all inputs.

I took three test cases L1 = [5, 4, 3, 2, 8], L2 = [5, 4, 3, 0, 8] and L3 = [4, 6, 1, 2, 5, 7] and performed the following steps:

1. Take the mean, x of all numbers except the last.

x1 = mean(L1') = 3.5
x2 = mean(L2') = 3
x3 = mean(L3') = 3.6
L' is the list excluding last number.

2. Perform ceil(x) and duplicate the list L into M

x1 = 4, x2 = 3, x3 = 4

3. Start from the center, M'[middle] do:

M[i] = --x if i < middle, else
M[i] = ++x if i > middle.

Find the maximum difference, m(which is the required answer) between each element of M[i] and L[i].

http://ideone.com/SwwXjm