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

Question

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

（见图片）

我的最简单的实现是O(n^3)：

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))，但我需要在线性时间内解决问题。另外，我不明白，是否有一种数学方法可以只查看数组并告诉上述总和的结果？

- Hamed_Gholami

---

"我应该用线性时间解决它。"甚至在看问题之前，第一个问题是，你确定这个问题可以在线性时间内解决吗？" - Abhinav Mathur

你可以提供一下问题的链接吗？ - Abhyuday Vaish

@AbhinavMathur 不是那样的，这是一个我们应该写代码解决的问题，如果不够快就会无法通过测试用例。每个人都应该使用Python编写自己的程序，以便公正地评判。 - Hamed_Gholami

这个问题可以在线性时间内解决；它与许多其他子数组问题非常相似，例如 这个问题，也可以在线性时间内解决。 - kcsquared

如果您知道并保存了最后t个元素的总和，则最后t+1个元素的总和只需要将单个值添加到该总和中即可--因此，具有线性时间。 - Cary Swoveland

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

这些条形图代表数值，数值越大，条形越长。在位置处的数值即将被添加。浅灰色的条形图是稍后添加的。绿色的条形图在栈中。棕色的条形图已经不再起作用。首先弹出-1位置处的条形图，但这不太具有信息性。然后弹出位置处的条形图。它支配着I[-1]和之间的范围：它是该范围内包含它的所有子数组中的最大值。这些子数组包含位置以及左侧的0到-1个元素和右侧的0到-1个元素。这是个子数组，它们的平均长度为<(a+b)/2>。

我临时将无穷大附加到数值上，以使其在左侧起到哨兵的作用（避免了while条件中的额外检查），并在末尾起到清理器的作用（它会导致所有剩余的数值从栈中弹出）。非Python编码人员：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

- Kelly Bundy

---

你说得完全正确，谢谢。但我还有最后一个问题，如果我想学习并自己解决这种类型的问题，您有什么建议吗？例如：任何课程、书籍、网站或练习。 - Hamed_Gholami

我会说像LeetCode这样的网站，它们有许多这样的问题，你可以看到并学习其他人的解决方案。 - Kelly Bundy

这真是太棒了；公式(a+b)*a*b//2用于计算子数组平均长度乘以子数组数量，非常巧妙。 - kcsquared