минимальное количество приращений диапазона для выравнивания всех элементов до максимального

Question

У меня вопрос о том, чтобы дать список из n целых чисел, на каждом шаге мы можем выбрать интервал (i, j), а затем увеличить на 1 все элементы, чтобы отбелить интервал.мы должны найти минимальное количество этой операции (выбрать интервал и т. д.), чтобы выровнять все элементы списка.Я уверен, что мы не должны увеличивать максимальное значение списка вообще.пример: [4 3 1 3 7] вывод: 6
3 раза [1 4], затем 1 раз [2 4] и, наконец, 2 раза [3 3], каков алгоритм, чтобы найти минимальное количество операций?

Answer 1

Вам нужно найти локальные минимумы и локальные максимумы. Количество необходимых операций будет: (max1 - min1) + (max2 - min2) + ...