为什么我找到增长最长的子序列而不是最长的递减子序列？

Question

我试图在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))

Answer 1

如果您对任何方式持开放态度，那么Wikipedia会有一些伪代码可以轻松转移到Python中并翻转以减少子序列。

N = len(X)
P = np.zeros(N, dtype=np.int)
M =  np.zeros(N+1, dtype=np.int)

L = 0
for i in range(0, N-1):
    # Binary search for the largest positive j ≤ L
    # such that X[M[j]] <= X[i]
    lo = 1
    hi = L
    while lo <= hi:
        mid = (lo+hi)//2

        if X[M[mid]] >= X[i]:
            lo = mid+1
        else:
            hi = mid-1
    # After searching, lo is 1 greater than the
    # length of the longest prefix of X[i]
    newL = lo

    # The predecessor of X[i] is the last index of 
    # the subsequence of length newL-1
    P[i] = M[newL-1]
    M[newL] = i
    #print(i)
    if newL > L:
        # If we found a subsequence longer than any we've
        # found yet, update L
        L = newL

# Reconstruct the longest increasing subsequence
S = np.zeros(L, dtype=np.int)
k = M[L]
for i in range(L-1, -1, -1):
    S[i] = X[k]
    k = P[k]

S

这给出了你追求的顺序

array([38, 20, 15, 14,  6])