线性时间内[所有子数组的最大值乘以其长度]的总和

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 个值的随机列表进行正确性测试（在线尝试！）：

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

Answer 2

def max_quality_of_team(N, Q): max_quality = float('-inf')

for start in range(N):
    current_sum = 0
    current_sum_square = 0
    
    for end in range(start, N):
        current_sum += Q[end]
        current_sum_square += Q[end] * Q[end]
        
        if end > start:
            quality = (current_sum * current_sum - current_sum_square) // 2
            max_quality = max(max_quality, quality)

return max_quality

N = int(输入(“”)) Q = list(map(int, input(" ").split()))

打印（团队的最大质量（N，Q）） 帮助我！