Какой алгоритм более эффективен для выравнивания вектора?

Для вектора из n элементов целого типа,каков более эффективный алгоритм, который производит минимальное количество шагов преобразования, в результате чего вектор, у которого все элементы равны, зная, что:

• за один шаг вы можете передать не более одной точки от элемента к его соседям ([ 0, 3, 0] -> [1, 2, 0] нормально, но не [0, 3, 0] -> [1, 1, 1]).
• на одном шаге элемент может получить 2 точек: один от его левого соседа и один справа ([3, 0, 3] -> [2, 2, 2]).
• первый элемент и последний элемент имеют только одного соседа, соответственно, 2-й элемент и элемент n-1.
• элемент не может быть отрицательным на любом этапе.

Примеры:

Given :
 0, 3, 0
Then 2 steps are required :
 1, 2, 0
 1, 1, 1

Given :
 3, 0, 3
Then 1 step is required :
 2, 2, 2

Given :
 4, 0, 0, 0, 4, 0, 0, 0
Then 3 steps are required :
 3, 1, 0, 0, 3, 1, 0, 0
 2, 1, 1, 0, 2, 1, 1, 0
 1, 1, 1; 1, 1, 1, 1, 1

Мой текущий алгоритм основан на суммах целых чисел с каждой стороны элемента. Но я не уверен, производит ли он минимальное количество шагов.

К вашему сведению, проблема является частью конкурса кода (созданного Criteo http://codeofduty.criteo.com ), который завершен. 11127227]