从O（n^2）到O（n）的最大减少列表

Question

我的程序的复杂性为O（n^2）。我想用复杂度O（n）来表示这个pogram。我怎样才能做到这一点

我的程序背后的想法是，我希望一个元素的列表与该元素之后的列表相比有最大的减少

例如，列表[4,7,5,8,4,3]将元素4与7,5,8,4,3进行比较，并将元素8与4,3进行比较。解决办法是；8-3=5（跌幅最大）

def grootste_daling(temperaturen):
    afname = []
    for i in range(len(temperaturen)):
        for j in range(i + 1, len(temperaturen),1):
                if temperaturen[i] - temperaturen[j] > 0:
                    afname.append(temperaturen[i] - temperaturen[j])
    return max(afname) if afname else 0

Answer 1

是的，这在线性时间内是可解的。您只需跟踪到目前为止看到的最大元素：

    maximum = 0
    max_decrease = 0
    for current in temperatures:
        if current > maximum:
            maximum = current
        if maximum - current > max_decrease:
            max_decrease = maximum - current

（0的初始值假设列表的值为正值，并且实际会减少。否则，可能需要以不同的方式初始化变量。）