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

Arnab Chakraborty

更新時間：22-12-2020

190 次檢視

開啟您的 職業生涯

透過完成該課程獲得認證

立即開始