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.

Since you are unconditionally inserting something in lis at every iteration it's no surprise your result is no less than the length of nums which suggests that something is wrong with your implementation. — Paul Panzer
– Paul Panzer, Commented Feb 10, 2018 at 7:38

Dlamini · Accepted Answer · 2018-02-11 10:19:44Z

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]))

Collectives™ on Stack Overflow

Longest Increasing Subsequence Efficient Algorithm Implementation in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related