最大最長遞增序列的

我有一個代碼，會發現一個列表的所有周期，例如，對於[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))

我會很感激的任何幫助。謝謝。

來源

2017-04-02 user422504

什麼是問題？ –

你有什麼問題嗎？ –

如何從這兩個功能去尋找每一個週期的LIS，然後再返回最大？ – user422504

這將做的工作：

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]

和

來源

2017-04-02 09:17:19

試試這個代碼：

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)))

來源

2017-04-02 11:03:04

最大最長遞增序列的

回答

相關問題