Блог

Я пытаюсь найти самую длинную убывающую подпоследовательность в массиве в 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))
 

Если вы открыты для любого способа взглянуть на это, в Википедии есть некоторый псевдокод, который легко переносится в 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])