2017-04-02 102 views
0

我有一个代码,会发现一个列表的所有周期,例如,对于[1,2,3]的周期是[1,2,3],[2,3,1] [3,1,2]。我也有一个寻找最长的子序列的代码。最大最长递增序列的

我想要做的是输入列表中,找到名单的每一个周期的最长递增子,然后返回最大长度的所有这些的。如何从这两个功能去寻找每一个周期的LIS,然后返回最大?

这是到目前为止我的代码:

def cycles(X): 

    n = len(X) 

    values = [] 

    for i in range(0,n): 
    values.append(X[i:n] + X[0:i]) 

    return values  



def longest_increasing_subsequence(d): 

    l = [] 

    for i in range(len(d)): 

     l.append(max([l[j] for j in range(i) if l[j][-1] < d[i]] or [[]], key=len) + [d[i]]) 


    return len(max(l, key=len)) 

我会很感激的任何帮助。谢谢。

+0

什么是问题? –

+0

你有什么问题吗? –

+0

如何从这两个功能去寻找每一个周期的LIS,然后再返回最大? – user422504

回答

1

这将做的工作:

l=[1,2,3,4] 
s=cycles(l) 
lis=[longest_increasing_subsequence(d) for d in s] 
print(lis) 
print(max(lis)) 

结果是

[4,3,2,3] 

4 
0

试试这个代码:

l = [3,4,5,9,8,1,2,7,7,7,7,7,7,7,6,0,1] 
empty = [] 
one = [1] 
two = [2,1] 
three = [1,0,2,3] 
tricky = [1,2,3,0,-2,-1] 
ring = [3,4,5,0,1,2] 
internal = [9,1,2,3,4,5,0] 

# consider your list as a ring, continuous and infinite 
def longest_increasing_subsequence(l): 
    length = len(l) 
    if length == 0: return 0 # list is empty 
    i, tmp, longest = [0, 1, 1] 
    # 1 < tmp means that ring is finished, but the sequence continue to increase 
    while i < length or 1 < tmp: 
     # compare elements on the ring 
     if l[i%length] < l[(i+1)%length]: 
      tmp += 1 
     else: 
      if longest < tmp: longest = tmp 
      tmp = 1 
     i += 1 
    return longest 

print("0 == " + str(longest_increasing_subsequence(empty))) 
print("1 == " + str(longest_increasing_subsequence(one))) 
print("2 == " + str(longest_increasing_subsequence(two))) 
print("3 == " + str(longest_increasing_subsequence(three))) 
print("5 == " + str(longest_increasing_subsequence(tricky))) 
print("5 == " + str(longest_increasing_subsequence(internal))) 
print("6 == " + str(longest_increasing_subsequence(ring))) 
print("6 == " + str(longest_increasing_subsequence(l)))