Pythonで少なくともk個の奇数を含む最長増加部分列の長さを求めるプログラム

本記事では、Pythonを使って「少なくともk個の奇数を含む最長増加部分列（LIS: Longest Increasing Subsequence）」の長さを求める方法を解説します。

問題の概要

数値のリスト nums と整数 k が与えられたとき、奇数がk個以上含まれる増加部分列の中で最も長いもののサイズを求めます。

例：

• 入力：nums = [12, 14, 16, 5, 7, 8]、k = 2
• 出力：3

この場合、奇数を2つ以上含む最長の増加部分列は [5, 7, 8] であり、その長さは3となります。

解法のアプローチ

この問題は、再帰的な動的計画法（メモ化なしの全探索型DP）を用いて解くことができます。基本的な考え方は以下の通りです。

1. 変数 best を0で初期化し、条件を満たす部分列の最大長を記録します。
2. 再帰関数 dp(i, j, odd, taken) を定義します。ここで各引数は次を意味します。
   • i: 現在の部分列の末尾要素のインデックス
   • j: 次に検討する候補要素のインデックス
   • odd: 現時点で部分列に含まれる奇数の個数
   • taken: 現時点での部分列の長さ
3. odd >= k の場合、best を max(best, taken) で更新します。
4. j がリストの末尾に達したら再帰を終了します。
5. nums[j] > nums[i] の場合（増加関係が成り立つ場合）、その要素を選んで再帰を続行します。このとき odd には nums[j] AND 1（奇数なら1、偶数なら0）を加算します。
6. 要素を選ばないケースとして、dp(i, j + 1, odd, taken) も呼び出し、すべての組み合わせを探索します。
7. メイン処理では、各インデックス i を起点として dp(i, i + 1, nums[i] AND 1, 1) を呼び出します。
8. 最後に best を返します。

実装例

以下にPythonによる実装例を示します。

class Solution:
    def solve(self, nums, k):
        best = 0

        def dp(i, j, odd, taken):
            nonlocal best
            # 奇数がk個以上あれば答えを更新
            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

計算量について

この実装はすべての部分列の組み合わせを探索するため、最悪の場合の時間計算量は O(2ⁿ) となります。リストのサイズが大きくなると非効率になるため、実用上はメモ化（functools.lru_cacheなど）や、状態 (i, odd_count) をキーとしたDPテーブルへの書き換えを検討すると良いでしょう。

まとめ

このように、再帰的な探索によって「増加関係」と「奇数の個数」という2つの制約を同時に満たす部分列を見つけることができます。ビット演算 & 1 を使うことで、偶奇の判定を簡潔に記述できる点もポイントです。