Why am I finding the longest increasing subsequence instead of the longest decreasing subsequence?

Question

I'm trying to look for the longest decreasing subsequence in an array in O(nlogn). Not sure whether this really takes O(nlogn), but anyways this returns the length of the longest increasing subsequence instead of the longest decreasing subsequence. Can anyone help?!?

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

If you are open to any way of looking at it, Wikipedia has some pseudocode which transferred easily into Python and flipped for decreasing subsequence.

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

Which gives the sequence you are after

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