python - O(n) 寻找最大差异总和的解决方案 python 3.x？

Question

我想知道，给定一个整数列表，比如说 l ，如果允许我们从这个列表中选择 3 个整数，比如 left , middle , right , 其中middle > left, right和 left, middle, right以该顺序出现在列表中(即 index(left)<index(middle)<index(right) )，是否存在 O(n)寻找 middle - left + middle - right 最大值的解决方案？您可能会认为不满足这些条件的列表不会出现(例如 Eric Duminil 指出的 [5, 0, 5])

目前，我能够想出我认为(大致)一个 O(n^2)解决方案(如果我错了请纠正我)。

基本上，我目前的想法是:

maximum = 0
for idx in range(1, N - 1):
    left = min(l[0: idx])
    right = min(l[idx + 1:])
    middle = l[idx]

    if left < middle and right < middle:
        new_max = middle - left + middle - right
        maximum = max(new_max, maximum)

帮助/提示将不胜感激。

谢谢!

Answer 1

您可以遍历您的数字一次，保留一个运行最小值，并在每一步存储它，以便在最后您知道每个索引左侧的最小值是多少。那是 O(n)。

同样，您可以从右到左遍历所有数字一次，并计算出每个索引右侧的最小值。即 O(n)。

然后您可以遍历每个可能的 middle 值，并从您之前的计算中获取 left 和 right 值。即 O(n)。

O(n) + O(n) + O(n) = O(n)。