Pythonで少なくともk個の奇数値を持つ最長増加部分列の長さを見つけるプログラム

numsと呼ばれる数値のリストと別の値kがあるとすると、少なくともk個の奇数要素を持つ最長増加部分列のサイズを見つける必要があります。

したがって、入力がnums =[12、14、16、5、7、8] k =2のような場合、出力は3になります。これは、少なくとも2つの奇数値を持つ最長増加部分列が[5、7 8]。

これを解決するには、次の手順に従います-

• 最高：=0

• 関数dp（）を定義します。これにはi、j、odd、takenが必要です

• 奇数>=kの場合、

  • ベスト：=ベストの最大値と取得

• jがnumsのサイズと同じである場合、

  • 戻る

• nums [j]> nums [i]の場合、

  • dp（j、j + 1、奇数+（nums [j] AND 1）、取得+ 1）

• dp（i、j + 1、奇数、取得）

• メインの方法から、次のようにします-

• 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