Python中最长的递增序列

如何使用Python中的N平方法和二进制搜索法计算一个数组中最长的递增子序列。

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

在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次。

在嵌套循环里面，我们将检查该值是否大于我们要检查的数字。然后，让我们把我们的nums_list 的i ，我们将更新nums_list 的值，同时使用最大值 nums_listi.

i 在外循环的迭代之后，对于 nums_listj,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 的平方，而空间复杂度将是o 的n 。

4

上面的解决方案已经足够了，但是另一种方法，n log ，使用二进制搜索到我们的临时数组的左边，使用bisect_left 。

from bisect import bisect_left
#Python小白学习交流群：153708845
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