Минимальные шаги, необходимые для уменьшения всех элементов массива до 1 на основе заданных шагов

Дан массив arr[] размера N . Задача состоит в том, чтобы найти минимальные шаги, необходимые для уменьшения всех элементов массива до 1. На каждом шаге выполните следующую заданную операцию:

• Выберите любой начальный индекс, скажем i , и перейдите к ( arr[i] + i ) ^th индексу, уменьшив ith , а также ( arr[i] + i ) ^th индекс на 1, следуйте этому процессу, пока он не достигнет конца массив
• Если элемент уже уменьшен до 1, его нельзя уменьшить больше, он остается прежним.

Примеры:

Input: arr[] = {4, 2, 3, 2, 2, 2, 1, 2}, N = 8
Output: 5
Explanation: Series of operations can be performed in the following way:

• {4, 2, 3, 2, 2, 2, 1, 2}, decrement values by 1, arr[] = {4, 2, 2, 2, 2, 1, 1, 1}
• {4, 2, 2, 2, 2, 1, 1, 1}, decrement values by 1, arr[] = {3, 2, 2, 2, 1, 1, 1, 1}
• {3, 2, 2, 2, 1, 1, 1, 1}, decrement values by 1, arr[] = {2, 2, 2, 1, 1, 1, 1, 1}
• {2, 2, 2, 1, 1, 1, 1, 1}, decrement values by 1, arr[] = {1, 2, 1, 1, 1, 1, 1, 1}
• {1, 2, 1, 1, 1, 1, 1, 1}, decrement values by 1, arr[] = {1, 1, 1, 1, 1, 1, 1, 1}

So, total steps required = 5

Input: arr[] = {1, 3, 1, 2, 2}, N = 5
Output: 2

Подход: Данную проблему можно решить, разделив ее на 4 части: - (от 0 до i-1) | я | (я + 1) | (от i + 2 до n – 1). Выполните следующие шаги, чтобы решить проблему:

1. Возьмите вектор, скажем, v , который будет обозначать, во сколько раз элемент уменьшается из-за посещения предыдущих элементов.
2. Каждый элемент в v т.е. v[i] обозначает количество уменьшения в arr[i] из-за посещения элементов от 0 до ( i-1 ).
3. Выполните итерацию по массиву arr[] и возьмите переменную, скажем, k для хранения количества проходов, которые должны быть добавлены в ответ из-за элемента arr[i] после того, как элементы от 0 до ( i-1 ) равны 1 .
4. Внутри цикла запустите еще один цикл (т.е. второй цикл), чтобы вычислить, насколько текущие элементы arr[i] влияют (уменьшаются после посещения i-го элемента) на ( i+2 ) до N элементов.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N ² )
Вспомогательное пространство : O(N)