问求所有连续子阵最大差和(S)的最优方法

EN

这可以在线性时间内完成！每个元素对于每个子数组，它是最大的，每个元素被减去一次，对于每个子数组，它是最小的。我们需要一个线性时间算法来找出每个元素有多少个子数组是最大或最小的，我们可以通过对所有最近的较小值算法的小修改来实现这一点。

我们的想法是，为了找出一个元素的最大子数组是多少，我们保留了一个元素堆栈，这些元素比我们看到的所有后续元素都要大，以及这些数字的位置。当我们发现一个元素大于堆栈上的最后一个元素时，我们知道子数组可以扩展到堆栈顶部的元素的左边或右边，并且它仍然是最大的，我们可以用它来确定它的最大子数组的数量。我们只需对数组中的所有元素进行消去，就可以处理最小值。

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]。然后，为了计算所有子数组的最大值之和，我们对输入进行如下迭代：

30

我们将这对(0, 30)推到堆栈上。堆栈现在记录了我们在索引0处看到了30。

10

30 > 10，所以我们将对(1, 10)推到堆栈上。堆栈现在记录了我们在索引1处看到了10。

40

10 < 40，因此最大为10的子数组不能包含此元素。我们发现，最大为10的子数组必须在索引30之后开始，在索引40之前结束，因此它有一个可能的左端点和一个可能的右端点，并且存在1*1这样的数组。我们将10*1*1添加到和中，并从堆栈中弹出(1, 10)。现在的总数是10。

30 < 40，因此最大为30的子数组也不能包含此元素。我们看到，最大为30的子数组必须启动索引0，并在索引0或索引1处结束，因此存在1*2这样的数组。我们将30*1*2加到和中，然后弹出(0, 30)。现在的总数是70。

堆栈现在是空的，所以我们按(2, 40)。

20

40 > 20，所以我们推(3, 20)。

我们已经迭代了所有输入，因此对于仍然在数组上的任何对(i, x)，具有最大x的子数组可以在从索引i到数组末尾的任何位置结束，并且可以从i开始到前一个堆栈条目的索引(如果没有前面的条目，则可以启动数组的开始)。

(3, 20)在堆栈中，它下面有(2, 40)，所以带max 20的子数组必须在索引3处开始和结束。我们将20*1*1添加到sum和pop (3, 20)中。总数现在是90。

(2, 40)在堆栈中，它下面什么都没有，所以一个带有max 40的子数组可以从任何索引<= 2开始，以任何索引>= 2结尾。我们将40*3*2添加到和中并空堆栈。现在的总数是330。

我们把所有的正数都记在总数上了。为了减去最小值，我们把所有的输入元素都去掉，然后再通过上面的算法给出它们。最后，我们减去170，总共160。

假设你有一个长度n的序列，你想要计算一个固定大小m< n的滑动窗口的最小(或最大值)，然后(令人惊讶地)，时间。

因此，对于窗口大小m= 1，…，n，您需要从左到右运行滑动窗口；对于窗口的每一张幻灯片，只需添加窗口内元素的最大值- min即可。根据以上情况，运行时间为Theta(n^2)。这改进了您的朴素算法，即Theta(n^3)。