Python中最长的递增子序列

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个未排序的整数列表。我们必须找到最长的增长子序列。因此，如果输入为[10,9,2,5,3,7,101,18]，则输出将为4，因为递增的子序列为[2,3,7,101]

为了解决这个问题，我们将遵循以下步骤-

• Trail：=长度为0到nums – 1的数组，并用0填充

• 大小：= 0

• 对于x的数字

• 中：= i +(j-i)/ 2

• 如果Trails [mid] <x，则i：= mid + 1，否则j：= mid

• i：= 0，j：=大小

• 当我不是j

• Trails [i]：= x

• 大小：= i + 1和大小的最大值

• 返回尺寸

让我们看下面的实现以更好地理解-

示例

class Solution(object):
   def lengthOfLIS(self, nums):
      tails =[0 for i in range(len(nums))]
      size = 0
      for x in nums:
         i=0
         j=size
         while i!=j:
            mid = i + (j-i)//2
            if tails[mid]< x:
               i= mid+1
            else:
               j = mid
               tails[i] = x
               size = max(i+1,size)
               #print(tails)
      return size
ob1 = Solution()print(ob1.lengthOfLIS([10,9,2,5,3,7,101,18]))

输入值

[10,9,2,5,3,7,101,18]

输出结果

4

以上是 Python中最长的递增子序列 的全部内容， 来源链接： utcz.com/z/357589.html