Найти исходный массив из заданного массива сумм префиксов

Дана префиксная сумма массива presum[] массива. Задача состоит в том, чтобы найти исходный массив, сумма префиксов которого равна presum[] .

Примеры:

Input:  presum[] = {5, 7, 10, 11, 18}
Output: [5, 2, 3, 1, 7]
Explanation: Original array {5, 2, 3, 1, 7} 
Prefix sum array = {5, 5+2, 5+2+3, 5+2+3+1, 5+2+3+1+7} = {5, 7, 10, 11, 18}
Each element of original array is replaced by the sum of the prefix of current index.

Input: presum[] = {45, 57, 63, 78, 89, 97}
Output: [45, 12, 6, 15, 11, 8] 

Подход: Эта проблема может быть решена на основе следующего наблюдения.

Given prefix sum array presum[] and suppose the original array is arr[] and the size is N.
The presum[] array is calculated as follows:

• presum[0] = arr[0]
• presum[i] = arr[0] + arr[1] + . . . + arr[i] for all i in range [1, N-1]

So, presum[i] = arr[0] + arr[i] + . . . + arr[i-1] + arr[i] 
                       = presum[i-1] + arr[i]
Therefore, arr[i] = presum[i] – presum[i-1]. for all i in range [1, N-1] and,
arr[0] = presum[0]

Выполните шаги, указанные ниже, чтобы решить проблему:

1. Пройдите массив presum[] , начиная с начала массива.
2. Если индекс (i) = 0 , то arr[i] = presum[i] .
3. В противном случае arr[i] = presum[i] – presum[i-1] .

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

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