最長遞增循環子序列

我有一個用於查找最長增加子序列的代碼，但是我想擴展這個以允許環繞。例如，對於序列（4,5,6,1,2,3），最長的遞增循環子序列是（1,2,3,4,5,6），因爲一旦我們達到3，我們就可以回到開始（我們只能這樣做一次。）有人能夠幫助我嗎？最長遞增循環子序列

下面是代碼：

def longest_increasing_subsequence(X): 

N = len(X) 
P = [0] * N 
M = [0] * (N+1) 
L = 0 
for i in range(N): 
    lo = 1 
    hi = L 
    while lo <= hi: 
     mid = (lo+hi)//2 
     if (X[M[mid]] < X[i]): 
      lo = mid+1 
     else: 
      hi = mid-1 

    newL = lo 
    P[i] = M[newL-1] 
    M[newL] = i 

    if (newL > L): 
     L = newL 

S = [] 
k = M[L] 
for i in range(L-1, -1, -1): 
    S.append(X[k]) 
    k = P[k] 
return len(S[::-1])

來源

2017-04-01 user422504

串連序列自身所具有的結束，然後在其上運行的算法。

來源

2017-04-01 21:25:14 Saigyouji

單從功能檢查每個班次返回值：

max_increasing=longest_increasing_subsequence(X) 
for i in range(len(X)-1): 
    X=X.append(X.pop(0)) #shift X by 1 
    if longest_increasing_subsequence(X)>max_increasing: 
     max_increasing=longest_increasing_subsequence(X)

來源

2017-04-01 21:30:30

最長遞增循環子序列

回答

相關問題