用 Python 编写程序来查找最长递增子序列的长度

pythonserver side programmingprogramming更新于 2026/1/23 22:36:17

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

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

创建一个名为 tails 的数组，其大小与 nums 相同，并用 0 填充。
size := 0
对于 nums 数组中的每个元素 x −
- i := 0, j := size
- 当 i 与 j 不同时，则
  - mid := i + (j – i)/2
  - 如果 tails[mid] < x，则 i := mid + 1，否则 j := mid
- tails[i] := x
- size := max ofi + 1 and size
返回 size。

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

示例

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))