如何使用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_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 的平方，而空间复杂度将是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
