python - 所有子数组的最大值乘以它们的长度的总和，线性时间

Question

给定一个数组，我应该在线性时间内计算以下总和:

我最天真的实现是 O(n³):

sum_ = 0

for i in range(n):
    for j in range(n, i, -1):
        sum_ += max(arr[i:j]) * (j-i)

我不知道该怎么办。我尝试了很多算法，但它们最多是 O(n*log(n))，但我应该在线性时间内解决它。另外，我不明白，有没有一种数学方法可以只查看数组并告知上述总和的结果？

Answer 1

保留一堆(索引)非递增值。因此，在附加新值之前，弹出较小的值。每当弹出一个时，将其贡献添加到总数中。

def solution(arr):
    arr.append(float('inf'))
    I = [-1]
    total = 0
    for i in range(len(arr)):
        while arr[i] > arr[I[-1]]:
            j = I.pop()
            a = j - I[-1]
            b = i - j
            total += (a+b)*a*b//2 * arr[j]
        I.append(i)
    arr.pop()
    return total

条形代表值，值越大，条形越大。 i 处的值即将被添加。浅灰色的较晚。绿色的在堆栈上。棕色的已经不起作用了。首先弹出位于 i-1 的那个，但信息量较少。然后 j 处的那个被弹出。它支配 I[-1] 和 i 之间的范围:它是包含它的该范围内所有子数组中的最大值。这些子数组包含 j 以及 0 到 a-1 左侧的更多元素和 0 到 b-1 右侧的更多元素。这是 a*b 子数组，它们的平均长度是 (a+b)/2。

我暂时将 infinity 附加到值上，这样它就可以作为左侧的哨兵(避免在 while 条件中进行额外检查)并作为最后的清洁器(它会导致所有剩余值从堆栈中弹出)。非 Python 编码人员:Python 支持负索引，-1 表示“最后一个元素”(倒数第一个)。

使用包含 500 个值的随机列表 (Try it online!) 进行正确性测试:

import random

def reference(arr):
    n = len(arr)
    return sum(max(arr[L : R+1]) * (R - (L-1))
               for L in range(n)
               for R in range(L, n))

for _ in range(5):
    arr = random.choices(range(10000), k=500)
    expect = reference(arr)
    result = solution(arr)
    print(result == expect, result)

示例输出(五个列表的结果，True 表示正确):

True 207276773131
True 208127393653
True 208653950227
True 208073567605
True 206924015682