Python 程序，用于找出至少 k 个奇数元素且最长的递增子序列的长度

假设我们有一个名为 nums 的数字列表和另一个值 k，我们必须找出至少有 k 个奇数元素的最长递增子序列的大小。

因此，如果输入为 nums = [12, 14, 16, 5, 7, 8] k = 2，则输出将为 3，因为至少有 2 个奇数元素的最长递增子序列是 [5, 7, 8]。

为解决此问题，我们将按以下步骤操作 −

  • best := 0

  • 定义一个函数 dp()。它将采用 i、j、odd 和 taken

  • 如果奇数 >= k，则

    • best := best 和 taken 的最大值

  • 如果 j 与 nums 的大小相同，则

    • 返回

  • 如果 nums[j] > nums[i]，则

    • dp(j, j + 1, odd +(nums[j] AND 1) , taken + 1)

  • dp(i, j + 1, odd, taken)

  • 从主方法执行以下操作 −

  • 对于从 0 到 nums 大小的 i 执行

    • dp(i, i + 1, nums[i] AND 1, 1)

  • 返回最佳值

示例 

让我们查看以下实现以增进理解 -

 在线演示

class Solution:
def solve(self, nums, k):
   best = 0
   def dp(i, j, odd, taken):
      nonlocal best
      if odd >= k:
         best = max(best, taken)
      if j == len(nums):
         return
      if nums[j] > nums[i]:
         dp(j, j + 1, odd + (nums[j] & 1), taken + 1)
      dp(i, j + 1, odd, taken)
   for i in range(len(nums)):
      dp(i, i + 1, nums[i] & 1, 1)
   return best
ob = Solution()
nums = [12, 14, 16, 5, 7, 8]
k = 2
print(ob.solve(nums, k))

输入

[12, 14, 16, 5, 7, 8], 2

输出

3

更新时间：22-12-2020

190 次查看

开启您的 职业生涯

通过完成该课程获得认证

立即开始
广告