我有一个寻找最长递增子序列的代码,但是我想扩展它以允许环绕。例如,对于序列(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])
只需在每次换班时检查函数的返回值:
将序列连接到其自身的末尾,然后在其上运行算法。在
相关问题 更多 >
编程相关推荐