查找所有连续子数组的最大差之和的最佳方法 [英] optimal way to find sum(S) of all contiguous sub-array's max difference

问题描述

为您提供了一个包含n个元素的数组:d[0], d[1], ..., d[n-1]. 计算所有连续子数组的最大差之和.

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.

形式上:S = 总和{max {d [l，...，r]}-min {d [l，...，r}} ，∀0< = l < = r< n

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

输入:

4 
1 3 2 4

输出:

12

说明:

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

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

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

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

l = 0; r = 2；数组:[1,3,2] sum = max([1,3,2])-min([1,3,2])= 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;数组:[1,3,2,4] sum = max([1,3,2,4])-min([1,3,2,4])= 4-1 = 3

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将导致零

l = 1; r = 1 will result in zero

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

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

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

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

l = 2; r = 2；将导致零

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

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

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

l = 3; r = 3将得出零；

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

总和= 12

我的想法: 蛮力检查所有可能的子集;传染性数组.

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

How to optimize it for larger number?

推荐答案

这可以在线性时间内完成！每个元素对最大的每个子数组求和一次，对每个元素的最小的子数组减去一次.我们需要一个线性时间算法来查找每个元素的最大或最小个数，并且我们可以对

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])

这是该算法的示例运行.假设输入为[30, 10, 40, 20].然后，为了计算所有子数组的最大值的总和，我们对输入进行如下迭代:

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

我们将对(0, 30)推入堆栈.现在，堆栈记录我们在索引0处看到了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，因此我们将对(1, 10)压入堆栈.现在，堆栈记录我们在索引1处看到了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，因此最大为10的子数组不能包含此元素.我们看到最大为10的子数组必须在索引30之后开始并在索引40之前结束，因此它有1个可能的左端点和1个可能的右端点，并且存在1*1这样的数组.我们将10*1*1添加到总和中，然后从堆栈中弹出(1, 10).现在总和为10.

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，因此最大为30的子数组也不能包含此元素.我们看到最大为30的子数组必须从索引0开始并在索引0或索引1处结束，因此存在1*2这样的数组.我们将30*1*2添加到总和中，然后弹出(0, 30).现在总和为70.

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.

堆栈现在为空，因此我们按下(2, 40).

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

20

40 > 20，所以我们按(3, 20).

我们已经遍历了所有输入，因此对于仍在数组中的任何对(i, x)，具有最大x的子数组可以从索引i到数组末尾的任何地方结束，并且可以在任何地方开始从i到上一个堆栈条目的索引(如果没有上一个条目，则为数组的开头).

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)在堆栈中，其下方是(2, 40)，因此具有最大20的子数组必须在索引3处开始和结束.我们将20*1*1添加到总和并弹出(3, 20).现在总和为90.

(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)在堆栈中，下面没有任何内容，因此具有最大40的子数组可以从任何索引<== 2开始并以任何索引> = 2结尾.我们将40*3*2加到总和上，清空堆栈.现在总和为330.

(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.

我们已经考虑了所有积极的条件.为了减去最小值，我们将所有输入元素取反，然后再次将它们输入上述算法.我们最终减去170，总共得到160.

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.

这篇关于查找所有连续子数组的最大差之和的最佳方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！