使用 Python 在大型整数列表中高效搜索最长升序子序列

发布于07月23日

我如何才能用Python语言开发一个高效且可伸缩的算法实现，以便在一大堆整数中找到最长的升序序列？我有一个包含数百万个元素的列表，而我当前的解决方案太慢了.以下是我当前的Python代码作为起点:

def longest_increasing_subsequence(nums):
    n = len(nums)
    lis = [1] * n
    for i in range(1, n):
        for j in range(0, i):
            if nums[i] > nums[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1

    max_length = max(lis)
    result = []

    for i in range(n - 1, -1, -1):
        if lis[i] == max_length:
            result.append(nums[i])
            max_length -= 1

    return result[::-1]

我注意到这个代码对于大的输入列表来说非常慢.有没有办法优化这个算法，甚至使用另一个算法，更适合在一个大的整数列表中寻找最长的升序序列？我对任何改善运行时间和内存要求的 idea 都持开放态度.提前谢谢！

推荐答案

如上所述，您的解决方案具有二次时间复杂性.然而，according to wikipedia在O(nlog(N))的时间复杂度内可以找到最优解.

我修复了我找到的here个代码，以获得以最佳时间复杂度运行的函数，并且我测试了结果与原始函数的一致性:

# Binary search
def GetCeilIndex(arr, T, l, r, key):
    while r - l > 1:
        m = l + (r - l) // 2
        if arr[T[m]] >= key:
            r = m
        else:
            l = m

    return r


def LongestIncreasingSubsequence(arr):
    n = len(arr)

    # Initialized with 0
    tailIndices = [0 for i in range(n + 1)]

    # Initialized with -1
    prevIndices = [-1 for i in range(n + 1)]

    # it will always point
    # to empty location
    length = 1
    for i in range(1, n):
        if arr[i] < arr[tailIndices[0]]:
            # new smallest value
            tailIndices[0] = i

        elif arr[i] > arr[tailIndices[length - 1]]:
            # arr[i] wants to extend
            # largest subsequence
            prevIndices[i] = tailIndices[length - 1]
            tailIndices[length] = i
            length += 1

        else:
            # arr[i] wants to be a
            # potential condidate of
            # future subsequence
            # It will replace ceil
            # value in tailIndices
            pos = GetCeilIndex(arr, tailIndices, -1, length - 1, arr[i])

            prevIndices[i] = tailIndices[pos - 1]
            tailIndices[pos] = i

    res = []
    i = tailIndices[length - 1]
    while len(res) < length:
        res.append(arr[i])
        i = prevIndices[i]
    res.reverse()

    return res