Python 查找循环递增子序列长度的程序

假设我们有一个名为 nums 的数字列表，我们需要查找最长递增子序列的长度，且假设该子序列可以环绕到列表的开头。

因此，如果输入类似于 nums = [6, 5, 8, 2, 3, 4]，则输出将为 5，因为最长递增子序列是 [2, 3, 4, 6, 8]。

为了解决这个问题，我们将按照以下步骤进行操作 -

  • a: 创建一个大小是 nums 两倍的列表，并填充两次 nums
  • ans: 0
  • 对于从 0 到 nums 的大小的 i，执行以下操作
    • dp: 一个新的列表
    • 对于从 i 到 nums 的大小 + i - 1 的 j，执行以下操作
      • n: a[j]
      • k: 将 n 插入 dp 的最左索引
      • 如果 k 与 dp 的大小相同时，则
        • 将 n 插入 dp 的末尾
      • 否则，
        • dp[k]:= n
      • ans: ans 的最大值和 dp 的大小
  • 返回 ans

让我们了解一下以下实现，以更好地理解 -

示例 

现场演示

import bisect
class Solution:
   def solve(self, nums):
      a = nums + nums
      ans = 0
      for i in range(len(nums)):
         dp = []
         for j in range(i, len(nums) + i):
            n = a[j]
            k = bisect.bisect_left(dp, n)
            if k == len(dp):
               dp.append(n)
            else:
               dp[k] = n
         ans = max(ans, len(dp))
      return ans

ob = Solution()
nums = [4, 5, 8, 2, 3, 4]
print(ob.solve(nums))

输入

[4, 5, 8, 2, 3, 4]

输出

5

更新于： 03-12-2020

133 次浏览

开启您的 职业生涯

完成课程获得认证

开始
广告