Сделать массив строго возрастающим, многократно вычитая и добавляя arr[i – 1] – (i – 1) к соседним индексам

Для заданного массива arr [] , состоящего из N положительных целых чисел, задача состоит в том, чтобы проверить, можно ли сделать данный массив arr[] строго возрастающим таким образом, что для любого индекса i из диапазона [1, N – 1] , если (arr[ i – 1] – (i – 1)) не меньше 0 , затем оно добавляется к arr[i] и вычитается из arr[i – 1] . Если можно сделать массив строго возрастающим, то выведите Yes . В противном случае выведите Нет .

Примеры:

Input: arr[] = {1, 5, 2, 7, 6}
Output: Yes
Explanation:
Consider the following operations:

1. Choosing the index 1, the value of arr[i – 1] – (i – 1) is 1, which is at least 0. Adding 1 to arr[1] and subtracting it from arr[0], modifies the array to {0, 6, 2, 7, 6}.
2. Choosing the index 2, the value of arr[i – 1] – (i – 1) is 5, which is at least 0. Adding 5 to arr[2] and subtracting it from arr[1], modifies the array to {0, 1, 7, 7, 6}.
3. Choosing the index 3, the value of arr[i – 1] – (i – 1) is 5, which is at least 0. Adding 6 to arr[3] and subtracting it from arr[2], modifies the array to {0, 1, 2, 12, 6}.
4. Choosing the index 4, the value of arr[i – 1] – (i – 1) is 9, which is at least 0. Adding 9 to arr[4] and subtracted from arr[3], modifies the array to {0, 1, 2, 3, 15}.

After the above operations, the array becomes strictly increasing.

Input: arr[] = {0, 1, 0}
Output: No

Подход: Данная проблема может быть решена с использованием жадного подхода. Следуйте инструкциям ниже, чтобы решить проблему

• Пройдите по заданному массиву, используя переменную i в диапазоне [1, N – 1] и выполните следующие шаги:
  • Если arr[i – 1] не меньше (i – 1) , выполните следующие шаги:
    • Сохраните значение arr[i] – arr[i – 1] в переменной, скажем, P.
    • Обновить arr[i – 1] как arr[i – 1] – P .
    • Обновить arr[i] как arr[i] + P .
• После выполнения вышеуказанных шагов, если массив arr[] отсортирован, то выведите «Да» . В противном случае выведите «Нет»

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

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