python3.x中求最大差和的O（n）解决方案？

Question

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

目前，我能够想出一个我认为（大致）的解决方案（如果我错了，请纠正我）。在

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

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和{}值。这是O（n）。在

O（n）+O（n）+O（n）=O（n）。在

Answer 2

诀窍在于列表的最小值总是解的一部分（要么左，要么右）。在

1. 找到列表的最小值，即O（n）。现在这个最小元素将是左或右。在
2. 找到最大值（2x-y），其中idx（x）>；idx（y）和idx（x）<；idx（min），即检查列表的左侧部分
3. 找到max（2x-y），其中idx（x）<；idx（y）和idx（x）gt；idx（min），即检查列表的右侧部分
4. 现在最多执行第2步和第3步，即左/中（或右/中）。在

Answer 3

这里有一种计算每个指数左右最小值的方法，用O（n）表示：

import random

N = 10
l = [random.randrange(N) for _ in range(N)]

print(l)
# => [9, 9, 3, 4, 6, 7, 0, 0, 7, 6]

min_lefts = []
min_left = float("inf")
min_rights = [None for _ in range(N)]
min_right = float("inf")

for i in range(N):
    e = l[i]
    if e < min_left:
        min_left = e
    min_lefts.append(min_left)

print(min_lefts)
# => [9, 9, 3, 3, 3, 3, 0, 0, 0, 0]

for i in range(N-1,-1,-1):
    e = l[i]
    if e < min_right:
        min_right = e
    min_rights[i] = min_right

print(min_rights)
# => [0, 0, 0, 0, 0, 0, 0, 0, 6, 6]

现在可以迭代l（idx之间的1和{}）中的每个中间元素，并找到2 * l[idx] - min_rights[idx] - min_lefts[idx]的最小值。此操作也是O（n）：

^{pr2}$

It输出：

11

它是2 * 7 - 0 - 3。在