python - 最长递增子序列高效算法Python实现

Question

我正在尝试为最长递增子序列编写一个高效的 0(nlogn) 算法:

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

但返回的答案是 7，而对数递增子序列 2 3 4 的长度为 3。

算法在最后描述在https://leetcode.com/problems/longest-increasing-subsequence/ .

我不明白为什么答案是 7，我的算法遵循正确的逻辑。

感谢您的帮助。

Answer 1

您的代码存在许多问题。首先，在方法中，

def lengthOfLISEfficient(nums):

当你说:

lis = [nums[0]]

您只将列表 [10,9,2,5,3,4] 的第一项发送到方法:

def whereToInsert(a, k):

而后一种方法用于在列表中定位数字。

这是一种不同的方法，涉及将主列表的每个子列表与该子列表的排序版本相匹配:

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