我试图在O(nlogn)中寻找数组中最长的递减子序列。不确定这是否真的需要O(nlogn),但无论如何,它返回最长递增子序列的长度,而不是最长递减子序列的长度。有人能帮忙吗?!?你知道吗
def binary_search(L, l, r, key):
while (r - l > 1):
m = l + (r - l)//2
if (L[m] >= key):
r = m
else:
l = m
return r
def LongestDecreasingSubsequenceLength(L, size):
tailTable = [0 for i in range(size + 1)]
len = 0
tailTable[0] = L[0]
len = 1
for i in range(1, size):
if (L[i] < tailTable[0]):
# new smallest value
tailTable[0] = L[i]
elif (L[i] > tailTable[len-1]):
tailTable[len] = L[i]
len+= 1
else:
tailTable[binary_search(tailTable, -1, len-1, L[i])] = L[i]
return len
L = [ 38, 20, 15, 30, 90, 14, 6, 7]
n = len(L)
print("Length of Longest Decreasing Subsequence is ",
LongestDecreasingSubsequenceLength(L, n))
如果您愿意以任何方式来看待它,Wikipedia有一些伪代码,可以很容易地转换到Python中,并翻转以减少子序列。你知道吗
它给出了你想要的序列
相关问题 更多 >
编程相关推荐