Минимизируйте абсолютную сумму, вычитая один и два из соседних индексов

Учитывая arr[] длины N , задача состоит в том, чтобы найти наименьшую возможную сумму массива, когда мы можем вычесть 1 и 2 соответственно из двух соседних индексов любое количество раз.

Примеры:

Input: N = 1, arr[] = { -45 }
Output: 45
Explanation: As there are no consecutive indices present, Therefore, operation can’t be performed, and the smallest possible value of absolute sum is 45.

Input: N = 3, arr[] = {4,  6, -1}
Output: 2
Explanation:
First Operation: Choose adjacent indices are 1, 2: {A₁ – 1, A₂ – 2, A₃} = {3, 4, -1}
Second Operation: Choose adjacent indices are 1, 2: {A₁ – 1, A₂ – 2, A₃} = {2, 2, -1}
Third Operation: Choose adjacent indices are 1, 2: {A₁ – 1, A₂ – 2, A₃} = {1, 0, -1}
Total smallest possible absolute sum: |1| + |0| + |-1| = 1 + 0 + 1 = 2.

Подход: реализуйте приведенную ниже идею, чтобы решить проблему.

The problem can be solved by traversing on arr[] using two for loops one by one and subtracting the values given in operations optimally 

It should be noted that the operation can be applied on the same indices until an non-optimal state of indices occur. Therefore, first we will try to reduce adjacent elements using operation multiple times at the same indices.    

• First Loop:
  Traverse from last to first index of arr[], if an element found greater than 1, then reduce arr[i] -= 2 * (arr[i] / 2) and arr[i-1] -=(arr[i] / 2)
  It can be possible that some adjacent elements are still there on which operation can be performed one more time. So we will check for those adjacent elements in second loop.
• Second Loop: Traverse from last to first index of arr[], if arr[i]>0 and arr[i-1]>0, then reduce arr[i] -= 2 and arr[i-1] -=1.

After applying two above loops, Just calculate the absolute sum of elements present in arr[] and print the sum.              

Для реализации идеи выполните следующие шаги:

• Запустить цикл на arr[] от последнего индекса к первому индексу и примените следующую концепцию:
  • Если arr[i] > 1, тогда установите arr[i] -= 2 * (arr[i]/2) и arr[i – 1] -= (arr[i]/2) .
• Запустите еще один цикл для arr[] от последнего индекса к первому индексу и примените следующую концепцию:
  • если arr[i] > 0 && arr[i – 1] > 0 , то уменьшить arr[i] -= 2 и arr[i – 1] -= 1 .
• Вычислить абсолютную сумму массива и вывести сумму.

Ниже приведена реализация описанного выше подхода.

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