1

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

我不是算法专家，但下面的代码不是 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]))]
4

1 回答 1

1

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

if sgn * lst[i] <= sgn * lst[i+1]:
于 2016-10-31T14:25:50.103 回答