У меня есть проблема, в которой у нас есть массив положительных чисел, и мы должны строго увеличивать его, внося ноль или более изменений в элементы массива.

Нас просят минимальное количество изменений, необходимых для строгого увеличения массива.

пример

если массив 1 2 9 10 3 15

поэтому ans = 1, если изменить 3 на некоторое число от 12 до 14.

если 1 2 2 2 3 4 5

ANS = 5

после изменения 2 на 3, затем от 2 до 4, затем от 3 до 5, затем от 4 до 6, затем от 5 до 7

Ограничения:

Количество элементов в массиве <= 10 ^ 6

Каждый элемент <= 10 ^ 9

Замечания:

Это не домашнее задание, его спросили в моем интервью, и я не смог дать алгоритм для него.

Может кто-нибудь дать мне алгоритм?

Ссылка на подробную проблему с примерами тестовых случаевhttps://www.hackerearth.com/problem/algorithm/find-path/

Поскольку это проблема mini / max, для меня это звучит как динамическое программирование, но мне нужна помощь.