Python中最长的递增序列
如何使用Python中的N平方法和二进制搜索法计算一个数组中最长的递增子序列。使用N平方法计算最长的递增子序列
在Python社区中，有一个著名的问题是关于最长递增子序列的，在不同的面试中也会被问到。这是一个Leetcode ，问题说：给定一个未排序的整数数组，找出该数组的最长递增子序列或子集的长度。
一个子集就像一个数组的短数组；每个数组可以有多个子集。另一件事是子数组将是这个 数组中的一些元素，但以连续的子序列方式。
它可以像 ，但不能像 ，所以在讨论子数组时不需要打破顺序。而且，在子序列中，元素在数组中出现的顺序必须是相同的，但可以是任何一个个体。
例如，在这种情况下，我们可以看到，答案是 ；5 ，但这是可以的，因为它是一个子序列。
如果我们看到从 开始的最长的递增子序列，我们会发现 ；这也可能意味着一个答案，但答案也可能是 ，这也是我们的另一个子序列。 也是一个子序列，但这不是最长的，所以我们不考虑它。
可能有不止一个组合；正如我们刚刚看到的，我们只需要返回长度。
通过这个例子，我们可以很容易地想到一个递归的解决方案，从零索引开始，沿着所有不同的路径进行。使用这个数组 ，我们可以采取，例如，用0 ，我们可以转到3 ，或者我们可以转到1 ，或者转到6 。
然后，从这一点开始，递归地继续下去。看看下面的例子，哪条路径最长，会是指数级的；我们很容易想到必须要有一些动态编程的方法。
所以，我们有一个数组，每个索引至少有一个长度。
我们将从第一个索引开始，0 ，其长度是1 ，但有了3 ，我们可以看后面，如果3 大于0 ，那么3 有2 的长度。如果我们再以1 ，我们将在当前索引之前的所有索引后面寻找。
从零索引中，我们可以看到1 大于0 ，但1 不大于3 ，所以在这一点上，我们要计算0 和1 ，其长度将是2 。
在考虑6 ，让我们从后面开始看，我们知道6 大于 或 ，包括6 ，其长度将是3 ，然后也是2 的长度是3 ，以此类推，这是一个平方的方法。
时间复杂度和空间复杂度
让我们跳入代码，创建我们的类，称为CalculateSubSequence ；在lengthOfLIS 函数里面，我们初始化我们的nums_list 变量为nums 的长度，这个数组将只有1次。
在嵌套循环里面，我们将检查该值是否大于我们要检查的数字。然后，让我们把我们的nums_list 的i ，我们将更新nums_list 的值，同时使用最大值 nums_list.
i 在外循环的迭代之后，对于 nums_list,j 是在内循环迭代后产生的，然后我们将其添加到1 中。最后，我们将返回nums_list 的最大值。
class CalculateSubSequence:
def lengthOfLIS(self, nums: list) -> int:
nums_list = * len(nums)
for i in range(len(nums)-1, -1, -1):
for j in range(i+1, len(nums)):
if nums < nums:
nums_list = max(nums_list, nums_list + 1)
return max(nums_list)
sbs = CalculateSubSequence()
sbs.lengthOfLIS()这里的时间复杂度将是n 的平方，而空间复杂度将是o 的n 。
4上面的解决方案已经足够了，但是另一种方法，n log ，使用二进制搜索到我们的临时数组的左边，使用bisect_left 。
from bisect import bisect_left
#Python小白学习交流群：153708845
class CalculateSubSequence:
def lengthOfLIS(self, nums: list) -> int:
n= len(nums)
tmp=]
for n in nums:
x = bisect_left(tmp,n)
if x ==len(tmp):
tmp.append(n)
elif tmp>n:
tmp=n
return len(tmp)
sbs = CalculateSubSequence()
sbs.lengthOfLIS()输出：
4
来源:https://www.cnblogs.com/xxpythonxx/p/17717656.html
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！
页:
[1]