线性时间内所有子阵列的最大值之和乘以其长度

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之间的范围：它是包含它的所有子阵列中的最大值。这些子阵列在左侧包含多个元素，在右侧包含多个元素。这就是a*b子阵列，它们的平均长度是a/b/2。

我暂时将无穷大附加到值，以便它在左侧作为哨兵（避免在while条件中进行额外检查）并在末尾作为清理器（它导致所有剩余值从堆栈中弹出）。非Python-coders：Python支持负索引，-1表示“最后一个元素”（从末尾开始的第一个）。

使用500个值的随机列表进行正确性测试（在线尝试！）：

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