程序以找到Python中最长的递增子序列的长度

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

假设我们有一个数字列表。我们必须找到最长的递增子序列的长度。因此，如果输入类似于[6、1、7、2、8、3、4、5]，则输出将为5，因为最长的递增子序列为[2,3,4,5,6]。

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

  • 制作一个名为tails的数组，其大小与nums相同，并用0填充。

  • 大小：= 0

  • 对于nums数组中的每个元素x-

    • 中：= i +（j – i）/ 2

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

    • i：= 0，j：=大小

    • 当我和j不一样时

    • 尾巴[i]：= x

    • 大小：=最大ofi + 1和大小

    • 返回大小。

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

    示例

    class Solution(object):
       def solve(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)
          return size
    ob = Solution()
    nums = [7, 2, 8, 3, 9, 4, 5, 6]
    print(ob.solve(nums))

    输入项

    [7, 2, 8, 3, 9, 4, 5, 6]

    输出结果

    5

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

    回到顶部