Python 中最长的递增子序列

假设我们有一个无序的整数列表。我们需要找出最长的递增子序列。所以，如果输入是 [10,9,2,5,3,7,101,18]，那么输出将是 4，因为递增子序列是 [2,3,7,101]

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

  • trail := 从长度为 0 到 nums - 1 的阵列，并用 0 填充它们
  • 大小 := 0
  • 对于 nums 中的 x
    • i := 0，j := 大小
    • while i 不等于 j
      • mid := i + (j - i) / 2
      • 如果 trails[mid] < x，则 i := mid + 1，否则 j := mid
    • 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

更新日期： 04-05-2020

3K+ 查看次数

开启你的 职业生涯

通过完成该课程获取认证

开始
广告