python - 最大的单调递增或递减子序列

Question

下面是我的最大单调子序列(增加或减少)的代码。在编写代码之前我没有做过任何研究，也不知道这是一个常见的计算机科学问题。从我随后的研究来看，似乎普遍接受的最有效算法是 O(N log N)。这些通常是动态规划类型的解决方案，此时我有点难以理解。

我不是算法专家，但下面的代码不就是O(N)吗？我遍历每个列表两次，一次查找递增序列，一次查找递减序列。

如果有任何关于清理它的建议，我也将不胜感激。我意识到这些功能非常重复，但我找不到一种很好的方法来一次性完成所有工作，而不重复第二个功能/ channel 。

def largest_monotonic_subsequence(lst):

    def increasing(lst):
        beg,end,best = 0,0,[0,0]
        for i in range(len(lst)-1):
            if lst[i] <= lst[i+1]:
                end = i+1
                if end - beg > best[1] - best[0]:
                    best = beg, end 
            else:
                beg = i+1
        return (best[0],best[1]+1)

    def decreasing(lst):
        beg,end,best = 0,0,[0,0]
        for i in range(len(lst)-1):
            if lst[i] >= lst[i+1]:
                end = i+1
                if end - beg > best[1] - best[0]:
                    best = beg, end 
            else:
                beg = i+1
        return (best[0],best[1]+1)

    incr = increasing(lst)
    decr = decreasing(lst)
    return lst[slice(*max([incr,decr], key = lambda x: x[1]-x[0]))]

Answer 1

您可以使用一个符号参数，设置为 +1 或 -1，来反转比较的含义

if sgn * lst[i] <= sgn * lst[i+1]: