optimal way to find sum(S) of all contiguous sub-array's max difference

Question

You are given an array with n elements: d[0], d[1], ..., d[n-1]. Calculate the sum(S) of all contiguous sub-array's max difference.

Formally: S = sum{max{d[l,...,r]} - min{d[l, ..., r}},∀ 0 <= l <= r < n

Input:

4 
1 3 2 4

Output:

12

Explanation:

l = 0; r = 0; array: [1] sum = max([1]) - min([1]) = 0

l = 0; r = 1; array: [1,3] sum = max([1,3]) - min([1,3]) = 3 - 1 = 2

l = 0; r = 2; array: [1,3,2] sum = max([1,3,2]) - min([1,3,2]) = 3 - 1 = 2

l = 0;r = 3; array: [1,3,2,4] sum = max([1,3,2,4]) - min([1,3,2,4]) = 4 - 1 = 3

l = 1; r = 1 will result in zero

l = 1; r = 2; array: [3,2] sum = max([3,2]) - min([3,2]) = 3 - 2 = 1;

l = 1; r = 3; array: [3,2,4] sum = max ([3,2,4]) - min([3,2,4]) = 4 - 2 = 2;

l = 2; r = 2; will result in zero

l = 2; r = 3; array:[2,4] sum = max([2,4]) - min([2,4]) = 4 -2 = 2;

l = 3; r = 3 will result in zero;

Total sum = 12

My Thoughts: Brute force check for all possible subset ; contagious array.

How to optimize it for larger number?

Answer 1

This can be done in linear time! Each element goes into the sum once for every subarray it's the max of, and each element is subtracted once for every subarray it's the minimum of. We need a linear-time algorithm for finding how many subarrays each element is the max or min of, and we can do that with a minor modification of an all nearest smaller values algorithm.

The idea is that to find how many subarrays an element is the max of, we keep a stack of the elements we've seen that are greater than all subsequent elements we've seen, along with the positions of those numbers. When we find an element greater than the last element on the stack, we know how far a subarray can extend to the left or right of the element on the top of the stack and still have it be the maximum, and we can use that to determine how many subarrays it's the max of. We can handle the minimums by simply negating all elements of the array.

def max_sums(d):
    stack = [(-1, float('inf'))]
    sum_ = 0
    for i, x in enumerate(d):
        while x > stack[-1][1]:
            prev_i, prev_x = stack.pop()
            prev_prev_i, prev_prev_x = stack[-1]
            sum_ += prev_x * (i - prev_i) * (prev_i - prev_prev_i)
        stack.append((i, x))
    while len(stack) > 1:
        prev_i, prev_x = stack.pop()
        prev_prev_i, prev_prev_x = stack[-1]
        sum_ += prev_x * (len(d) - prev_i) * (prev_i - prev_prev_i)
    return sum_

def max_differences_sum(d):
    return max_sums(d) + max_sums([-x for x in d])

Here's an example run of the algorithm. Suppose the input is [30, 10, 40, 20]. Then to compute the sum of the maxes of all subarrays, we iterate over the input as follows:

30

We push the pair (0, 30) onto the stack. The stack now records that we saw a 30 at index 0.

10

30 > 10, so we push the pair (1, 10) onto the stack. The stack now records that we saw a 10 at index 1.

40

10 < 40, so a subarray with max 10 cannot include this element. We see that a subarray with max 10 must start after the index of 30 and end before the index of 40, so it has 1 possible left endpoint and 1 possible right endpoint, and there is 1*1 such array. We add 10*1*1 to the sum and pop the (1, 10) from the stack. The sum is now 10.

30 < 40, so a subarray with max 30 also cannot include this element. We see that a subarray with max 30 must start index 0 and end at either index 0 or index 1, so there are 1*2 such arrays. We add 30*1*2 to the sum and pop the (0, 30). The sum is now 70.

The stack is now empty, so we push (2, 40).

20

40 > 20, so we push (3, 20).

We have iterated through all the input, so for any pair (i, x) still on the array, a subarray with max x can end anywhere from index i to the end of the array, and it can start anywhere from i to the previous stack entry's index (or the start of the array if there is no previous entry).

(3, 20) is on the stack with (2, 40) beneath it, so a subarray with max 20 must start and end at index 3. We add 20*1*1 to the sum and pop (3, 20). The sum is now 90.

(2, 40) is on the stack with nothing beneath it, so a subarray with max 40 can start at any index <= 2 and end at any index >= 2. We add 40*3*2 to the sum and empty the stack. The sum is now 330.

We've accounted for all positive terms in the sum. To subtract the minimums, we negate all input elements and feed them through the above algorithm again. We end up subtracting 170, for an overall total of 160.