求所有相邻子数组最大差之和的最佳方法

Question

您将获得一个包含n个元素的数组：<代码>d[0]，d[1]。。。，d【n-1】。计算所有相邻子数组的最大差值之和。

形式上：S=sum{max{d[l，...， r]}-min{d[l，...， r}}，Δ0

输入：

4 
1 3 2 4

输出：

12

解释：

l=0；r=1；数组：[1,3]和=最大值（[1,3]）-最小值（[1,3]）=3-1=2

l=0；r=2；数组：[1,3,2]和=最大值（[1,3,2]）-最小值（[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=1；r=1将导致零

l=1；r=2；数组：[3,2]和=最大值（[3,2]）-最小值（[3,2]）=3-2=1；

l=1；r=3；数组：[3,2,4]和=最大值（[3,2,4]）-最小值（[3,2,4]）=4-2=2；

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

l=2；r=3；数组：[2,4]和=最大值（[2,4]）-最小值（[2,4]）=4-2=2；

l=3；r=3将导致零；

总计=12

我的想法：暴力检查所有可能的子集；传染性阵列。

How to optimize it for larger number?

Answer 1

假设您有一个长度为n的序列，并且您希望计算某个固定大小m的滑动窗口的最小值（或最大值）

现在对于窗口大小m=1。。。，n、 您需要从左向右运行滑动窗口；对于窗口的每个幻灯片，您只需要添加窗口内元素的最大-最小值。如上所述，运行时间为θ（n^2）。这改进了原始算法，即θ（n^3）。

Answer 2

这可以在线性时间内完成！每个元素对每个子数组进行一次求和，它是最大值，每个元素对每个子数组减去一次，它是最小值。我们需要一个线性时间算法来确定每个元素的最大或最小值是多少个子数组，我们可以通过对所有最近的较小值算法进行小修改来做到这一点。

这个想法是，为了找出一个元素的最大值是多少个子数组，我们保留了一堆我们看到的大于我们看到的所有后续元素的元素，以及这些数字的位置。当我们找到一个大于堆栈上最后一个元素的元素时，我们知道一个子数组可以扩展到堆栈顶部元素的左边或右边多远，并且仍然是最大值，我们可以用它来确定它是多少个子数组的最大值。我们可以通过简单地否定数组的所有元素来处理最小值。

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

40

<代码>10

<代码>30

堆栈现在是空的，所以我们推（2，40）。

20

<代码>40

我们已经遍历了所有输入，因此对于仍在数组上的任何对（i， x），具有maxx的子数组可以在从indexi到数组末尾的任何位置结束，并且它可以从i到前一个堆栈条目的索引（如果没有前一个条目，则为数组的开始）的任何位置开始。

（3，20）位于堆栈上，其下方为（2，40），因此最大值为20的子阵列必须从索引3开始和结束。我们将20*1*1加到总和中，然后弹出（3，20）。总数现在是90。

（2,40）在堆栈上，下面没有任何东西，因此最大40的子数组可以从任何索引开始

我们已经考虑了总和中的所有正项。为了减去最小值，我们否定所有输入元素，并再次通过上述算法提供它们。我们最终减去170，总共160个。