## § Sum of absolute differences of an array

• We are given an array a[:] and we are asked to compute the sum of differences $\sum_{i=1}^n \sum_{j=i+1}^n |a[i] - a[j]|$.
• To compute this efficiently, first sort a[:] into a sorted array s[:]. For simplicity, say we have N = 4.
• Now see that if we write down the values for N=4, we will see:
D =
|s - s| + |s - s| + |s - s| +
|s - s| + |s - s| +
|s - s|

• i < j implies s[i] < s[j] as s is sorted. So each of the terms (s[i] - s[j]|) is negative. We thus flip the terms, giving:
D =
(s - s) + (s - s) + (s - s) +
(s - s) + (s - s) +
(s - s)

• Note that s is always negative, so it will have coefficient -4 on grouping.
• See that s was positive in the grouping (1, 2), and was negative in the groupings (2, 3) and (2, 4). So 2 will have a coefficient +1*(2-1) -1*(4 - 2).
• Similarly, s was positive in the grouping (1, 3) and (2, 3) and was negative in the grouping (3, 4).
• In general, s[i] will be positive when paired with [1, 2, ..i-1, i) and negative when paired with (i, i+1, i+2, \dots n]. So s[i] will contribute a coefficient of +1*(i-1) - 1*(n-i)[using the formula that for intervals [l, r) and (l, r] the number of elements is (r-l)]