最长递增循环子序列

我有一个用于查找最长增加子序列的代码，但是我想扩展这个以允许环绕。例如，对于序列（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

最长递增循环子序列

回答

相关问题