给定一个数组,我应该在线性时间内计算以下总和:
(见图片)
我的最简单的实现是O(n^3):
(见图片)
我的最简单的实现是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)),但我需要在线性时间内解决问题。另外,我不明白,是否有一种数学方法可以只查看数组并告诉上述总和的结果?
t
个元素的总和,则最后t+1
个元素的总和只需要将单个值添加到该总和中即可--因此,具有线性时间。 - Cary Swoveland