在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参数。
如果odd ≥ 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)
在主方法中执行以下操作 –
对于i在范围0到nums列表的大小中的操作如下所示 –
- dp(i，i + 1，nums[i] AND 1，1)
返回best

例子

让我们看一下以下实现以更好地理解 –

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