最大的依次递增或递减

Question

下面是我对最大单调子序列（增加或减少）的代码。在编码之前，我没有做过任何研究，也不知道这是一个常见的计算机科学问题。从我后来的研究来看，目前公认的最有效的算法是O（nlogn）。这些都是典型的动态编程类型的解决方案，我现在有点不知所措。在

我不是算法专家，但下面的代码不是O（N）吗？我对每个列表进行两次遍历，一次查找递增序列，一次查找递减序列。在

我也希望你能给我一些关于清理的建议。。我意识到这些功能是非常重复的，但是如果不重复第二个函数/过程，我就找不到一次完成所有任务的好方法。在

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

您可以使用符号arg（设置为+1或-1）来反转比较的意义

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