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？您可能会认为不符合这些条件的列表不会出现(例如[5,0,5],如Eric Duminil所指出的那样)

目前,我能够提出我认为(大致)一个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).

Answer 2

你绝对走在正确的轨道上，你只需要摆脱那些最小的操作。所以我给你的提示是，你可以预先计算它们（以线性时间），然后在循环中查找最小值，就像你已经在做的那样。

澄清一下：您必须在已有的部分之前min(list[0:i])预先计算min(list[i:n])所有i内容。这个想法是将它们存储在两个数组中，例如和，这样和。然后，在循环中使用andm1m2m1[i] = min(list[0:i])m2[i] = min(list[i:n])m1m2

现在的挑战是在线性时间内计算m1和m2，这意味着您不允许使用该min函数来计算它们。如果有m1[i]，你如何计算m1[i+1]使用list[i+1]？