下面是我的最大单调子序列(增加或减少)的代码。在编写代码之前我没有做过任何研究，也不知道这是一个常见的计算机科学问题。从我随后的研究来看，似乎普遍接受的最有效算法是 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]))]
最佳答案
您可以使用一个符号参数，设置为 +1 或 -1，来反转比较的含义
if sgn * lst[i] <= sgn * lst[i+1]:
关于python - 最大的单调递增或递减子序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40337207/