返回顶部

收藏

寻找递增最长子序列

更多

找n个正整数的序列中最长的单调递增子序列,看《算法导论》用Python写来练手,不知道正确否。如有错误,望各位大神指正。

def longest_sub_increase_seq(array):
    #求最长子序列,array为length个数的序列#
    length = len(array)
    x=[1 for i in range(length)]  #保存前i个序列的最长数量,每个序列至少长度为1
    z=[0 for i in range(length)]  #保存对于第i个数来说,
    for i in range(1,length):
        index=i    #记录使x[0..i]递增子序列最长的,倒数第二个位置
        maxnum=1   #递增序列的长度
        for j in range(i):
            if array[i]>array[j]:
                if maxnum<x[j]+1:
                    index=j
                    maxnum=x[j]+1

        z[i]=index
        x[i]=maxnum
    maxvlaue=max(x)

    return_value=[]
    for i in range(length):
        vv=[]
        if x[i]==maxvlaue:
            j=i
            while z[j]!=j:
                vv.append(array[j])
                j=z[j]
            else:
                vv.append(array[j])
            return_value.append(vv)

    return return_value
#该片段来自于http://outofmemory.cn

标签:python,算法

收藏

0人收藏

支持

0

反对

0