Longest Increasing Subsequence Efficient Algorithm Implementation in Python

Question

I am trying to write an efficient 0(nlogn) algorithm for longest increasing subseuqnce:

def whereToInsert(a, k):
    l, r = 0, len(a)-1
    while l<=r:
        m = l + (r-l)//2
        if a[m]==k:
            return m
        elif a[m]>k:
            r = m - 1
        else:
            l = m + 1

    if l==len(a)-1:
        return l+1
    else:
        return l

#print(whereToInsert([1,2,3,4,5,6,7,8,9], 0.5)) #This works fine

def lengthOfLISEfficient(nums):
    lis = [nums[0]]
    for x in nums[1:]:
        t = whereToInsert(lis,x)
        if t>=len(lis):
            lis.append(0)
        lis.insert(t, x)

    return len(lis)

print(lengthOfLISEfficient([10,9,2,5,3,4]))

But the answer returned is 7 whereas the logest increasing subsequence 2 3 4 is of length 3.

The algorithm is described at the end in https://leetcode.com/problems/longest-increasing-subsequence/.

I am not getting why the answer is coming 7, my algorithm is following the correct logic.

Thanks for your help.

Answer 1

There are a number of issues with your code. Firstly, in the method,

def lengthOfLISEfficient(nums):

when you state:

lis = [nums[0]]

you send only the first item of the list [10,9,2,5,3,4] to the method:

def whereToInsert(a, k):

whereas the latter method is meant to position a number within a list.

Here is a different approach, which involves matching each sublist of the main list with a sorted version of that sublist:

def lengthOfLISEfficient(nums):
    #lis = [nums[0]]
    lisList = []
    for h in range(len(nums)-1):
        lis = []
        #numberNow = nums[h]
        addableLength = len(nums) - h
        #lis.append(numberNow)
        for f in range(addableLength):
            additem = nums[h+f]
            lis.append(additem)
        lisList.append(lis)
    print(lisList)  #just for check, feel free to delete this line
    subsequenceList = []
    for list in lisList:
        sortedList = list.copy()
        sortedList.sort()
        subsequence = []
        for e in range(len(list)):
            if len(subsequence) > 0:
                if prev <= list[e] and sortedList.index(list[e]) == index+1:
                    subsequence.append(list[e])
                else:
                    continue
            else:
                subsequence.append(list[0])
            prev = list[e]
            index = sortedList.index(prev)
        subsequenceList.append(subsequence)
    print(subsequenceList)  #just for check, feel free to delete this line
    lengths = []
    for l in range(len(subsequenceList)):
        lengths.append(len(subsequenceList[l]))
        if len(lengths) == len(subsequenceList):
            longest = max(lengths)
            longestSublist = subsequenceList[lengths.index(longest)]
    return longest, longestSublist  # Don't return longestSublist if you do not want it

print(lengthOfLISEfficient([10,9,2,5,3,4]))