Сумма абсолютных разностей чисел в массиве ⇐ Python

[Anonymous]

Я хочу вычислить сумму абсолютных разностей числа с индексом i со всеми целыми числами до индекса i-1 в o(n). Но я не могу придумать какой-либо подход лучше, чем o(n^2) .
Например:
[3, 5, 6, 7, 1]

массив с абсолютной суммой будет (для целого числа с индексом i сумма будет с индексом i в другом массиве):
[0, 2, 4, 7, 17]

Может ли кто-нибудь помочь мне уменьшить сложность до o(n) (если это невозможно, то хотя бы лучшая оптимизация с точки зрения временной сложности)?
Вот мой код Python:
a = [3, 5, 6, 7, 1]
n = 5
absoluteSumArray = []
for i in range(n):
Sum = 0
for j in range(i):
Sum += abs(int(a) - int(a[j]))
absoluteSumArray.append(Sum)


Подробнее здесь: https://stackoverflow.com/questions/229 ... n-an-array