最長増加サイクリックサブシーケンス

Question

私は、最も長い増加サブシーケンスを見つけるためのコードを持っていますが、これをラップアラウンドできるように拡張したいと思います。例えば、シーケンス（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]) 

Answer 1

はそれであなたのアルゴリズムを実行し、自身の最後にシーケンスを連結します。ここでは

コードがあります。

Answer 2

ただ、各シフトに関数から返される値を確認します

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) 

を