Минимальные приращения или уменьшения, необходимые для знаков чередования элементов массива сумм префиксов

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

Примеры:

Input: arr[] = {1, -3, 1, 0}
Output: 4
Explanation:
Following are the operations performed on the given array elements:

1. Incrementing the array element arr[1](= -3) by 1 modifies the array to {1, -2, 1, 0}.
2. Incrementing the array element arr[2](= 1) by 1 modifies the array to {1, -2, 2, 0}.
3. Decrementing the array element arr[3](= 0) by 1 modifies the array to {1, -2, 2, -1}.
4. Decrementing the array element arr[3](= -1) by 1 modifies the array to {1, -2, 2, -2}.

After the above operations, the prefix sum of the modified array is {1, -1, 1, -1}, which is in alternate order of sign. Therefore, the minimum number of operations required is 4.

Input: arr[] = {3, -6, 4, -5, 7}
Output: 0

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

• Для случая 1: изменение элемента массива в порядке отрицательного, положительного, отрицательного:
  1. Инициализируйте переменные current_prefix_1 равными 0 , в которых хранится сумма префиксов массива.
  2. Инициализируйте переменные minOperationCase1 равными 0 , в которых хранится результирующее минимальное количество требуемых операций.
  3. Пройдите по заданному массиву и выполните следующие шаги:
     • Увеличьте current_prefix_1 на arr[i] .
     • Если значение current_prefix_1 или четности равно -ve, то увеличьте минимальное количество операций на abs(parity – current_prefix_1) .
     • Умножьте четность на (-1) .
• Точно так же, как обсуждалось в случае 1, найдите минимальное количество операций, необходимых для порядка суммы префиксов как положительный, отрицательный, положительный, … и сохраните его в переменной minOperationCase2 .
• После выполнения вышеуказанных шагов выведите минимум minOperationCase1 и minOperationCase2 в качестве требуемых результирующих операций.

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

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