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

Question

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

$\Big(\sum_{l=1}^n\sum_{r=l}^n \max\big(arr[l..r])\times (r - (l - 1)) \Big)$

我最天真的实现是 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

保留一堆 non-increasing 值的（索引）。因此，在附加新值之前，弹出较小的值。每当弹出一个时，将其贡献添加到总数中。

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 条件下进行额外检查）和清洁器结束（它会导致所有剩余的值从堆栈中弹出）。 Non-Python-coders：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

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

Sum of the maximums of all subarrays multiplied by their lengths, in linear time

python

arrays

algorithm

math

time-complexity