在Python中找到所有最大单调子序列

Question

现在我在尝试找出序列中所有的最大子序列（包括正数和负数）。我遇到了一些问题，因为没有找到合适的解决方案。我有这段代码，但输出结果只对正数有效。由于我刚开始学习Python，所以暂时无法快速找到解决办法。

testcase = [1,2,3,4,5,4,3,2,1,0,-1,-2,-3,-2,-1,-2,-1,-2,-3,-4,-5]
def process(lst):
    def sub(lst):
        temp = []
        while lst and (not temp or temp[-1] <= lst[0]):
            temp.append(lst[0])
            lst = lst[1:]
        return temp, lst

    res=[]
    while lst:
        subres, lst = sub(lst)
        res.append(subres[0] if len(subres)==1 else subres) 
    return res
if __name__ == "__main__":
    print(process(testcase))

所以，示例输出是

[[1, 2, 3, 4, 5], 4, 3, 2, 1, 0, -1, -2, [-3, -2, -1], [-2, -1], -2, -3, -4, -5]]

而我想要的结果是

[[1,2,3,4],[5,4,3,2,1,0,-1,-2,-3],[-2,-1],-2,[-1,-2,-3,-4,-5]]

所以，我的问题是，这该怎么做呢？

Answer 1

你基本上需要跟踪“导数”（元素之间的差异），并观察它何时改变方向。

你可以使用 numpy 很简洁地表达这一点：

import numpy as np
np_split_indexes= np.where(np.diff(np.diff(testcase))!=0)[0]+2
split_indexes= [0] + list(np_split_indexes) + [len(testcase)]
result= [testcase[a:b] for a,b in zip(split_indexes[:-1],split_indexes[1:])]

或者，如果你更喜欢纯 Python 的话：

result=[]
tmp=[]
last_direction=0;
last_element=0;
for x in testcase:
    direction= (x-last_element)/abs(x-last_element) #math trick - divide by the magnitude to get the direction (-1/1)
    last_element= x
    if (direction!=last_direction) and tmp:
        result.append(tmp)
        tmp=[]
    last_direction= direction
    tmp.append(x)
if tmp:
    result.append(tmp)

print result

输出结果：

[[1, 2, 3, 4, 5], [4, 3, 2, 1, 0, -1, -2, -3], [-2, -1], [-2], [-1], [-2, -3, -4, -5]]

注意，这与你想要的输出在最后有些不同。我不太明白你为什么把 -1 放在最后一组，因为它是一个局部最大值。