迹忆客 专注技术分享

我们将学习什么是子序列，以及如何使用 Python 中的 n 平方方法和二分搜索方法计算数组中最长的递增子序列。

使用 N 平方方法计算 Python 中的最长递增子序列

一个著名的问题被问及 Python 社区中最长的增长子序列，并在不同的采访中被问及。 这是一个 Leetcode 问题，问题是：给定一个未排序的整数数组，并找到给定数组的最长递增子序列或子集的长度。

子集就像数组的短数组； 每个数组可以有多个子集。 另一件事是子数组将是此 [10,9,2,5,3,7,101,18] 数组中的一些元素，但以连续的子序列方式。

可以是[2, 3, 5, 7]，但不能是[2,3,101]，所以讨论子数组时不需要打断序列。 并且，随后，元素在数组中出现的顺序必须相同，但可以是任何一个。

例如，在本例中，正如我们所见，答案是 [2, 3, 7,101]； 5 不存在，但这没关系，因为它是一个子序列。

如果我们从 [10,9,2,5,3,7,101,18] 中看到最长的递增子序列，我们会找到 [2, 5, 7, 101]； 这也可能意味着一个答案，但答案也可能是 [2, 3, 7, 101] 这也是我们的另一个子序列。 [3, 7, 101] 也是一个子序列，但不是最长的，所以不考虑。

可能有不止一种组合； 正如我们刚刚看到的，我们只需要返回长度。

通过这个例子，我们可以很容易地想到一个递归解决方案，从零索引开始，沿着所有不同的路径前进。 使用这个数组 [0,3,1,6,2,2,7]，我们可以采取，例如，对于 0，我们可以转到 3，或者我们可以转到 1 或转到 6。

然后，从那时起，递归地继续。 看下面的例子，哪条路径是最长的，它将是指数级的； 我们很容易认为必须有一些动态编程方法。

所以，我们有一个数组，其中每个索引至少有一个长度。

[0,3,1,6,2,2,7]
[1,1,1,1,1,1,1]

我们将从第一个索引 0 开始，其长度为 1，但是对于 3，我们可以向后看，如果 3 大于 0，则 3 有 2 个长度。 如果我们再次使用 1，我们将查看当前索引之前的所有索引。

从零索引可以看出，1大于0，但1不大于3，所以此时我们计算0和1，它们的长度为2。

[0,3,1,6,2,2,7]
[1,2,2,1,1,1,1]

在考虑6的时候，我们从头往后看，我们知道6大于[0,1]或者[0,3]，加上6，它的长度就是3那么2的长度也是3，以此类推 对了，这是一个平方的方法。

[0,3,1,6,2,2,7]
[1,2,2,3,3,...]

时间复杂度和空间复杂度

让我们进入代码并创建名为 CalculateSubSequence 的类； 在 lengthOfLIS 函数中，我们将 nums_list 变量初始化为 nums 的长度，数组的长度仅为 1 次。

在嵌套循环中，我们将检查值是否大于我们正在检查的数字。 然后，让我们取 i 的 nums_list，我们将更新 nums_list 值，同时使用 nums_list[i] 取最大值。

i 在从外循环迭代之后出现，对于 nums_list[j]，j 在从内循环迭代之后出现，然后我们将它加 1。 最后，我们返回 nums_list 的最大值。

class CalculateSubSequence:

    def lengthOfLIS(self, nums: list[int]) -> int:

        nums_list = [1] * len(nums)

        for i in range(len(nums)-1, -1, -1):

            for j in range(i+1, len(nums)):

                if nums[i] < nums[j]:

                    nums_list[i] = max(nums_list[i], nums_list[j] + 1)

        return max(nums_list)

sbs = CalculateSubSequence()
sbs.lengthOfLIS([0,3,1,6,2,2,7])

这里时间复杂度是 n 的平方，空间复杂度是 n 的 o。

4

上面的解决方案就足够了，但另一种方法 n log 使用 bisect_left 对临时数组的左侧进行二进制搜索。

from bisect import bisect_left

class CalculateSubSequence:

    def lengthOfLIS(self, nums: list[int]) -> int:
        n= len(nums)
        tmp=[nums[0]]
        for n in nums:
            x = bisect_left(tmp,n)
            if x ==len(tmp):
                tmp.append(n)
            elif tmp[x]>n:
                tmp[x]=n
        return len(tmp)

sbs = CalculateSubSequence()
sbs.lengthOfLIS([0,3,1,6,2,2,7])

输出:

4