C++で正確にk個の奇数を含む最長部分配列を求める方法

問題の概要

n個の要素からなる配列が与えられたとき、正確にk個の奇数を含む最長の部分配列（サブ配列）の長さを求めるのがこの問題です。

例として、A = [2, 3, 4, 11, 4, 12, 7]、k = 1 の場合を考えてみましょう。このとき答えは 4 となり、該当する部分配列は [4, 11, 4, 12] です（含まれる奇数は 11 の1個だけです）。

アルゴリズム：スライディングウィンドウ

この問題はスライディングウィンドウ（尺取り法）を使うことで効率的に解けます。全体の計算量は O(n) に抑えられます。手順は以下の通りです。

• max := 0、count := 0、start := 0 として初期化する
• i を 0 から n − 1 まで順に処理する
  • arr[i] が奇数（arr[i] mod 2 ≠ 0）なら、count を 1 増やす
  • count > k かつ start ≤ i の間、次を繰り返す
    • arr[start] が奇数なら count を 1 減らす
    • start を 1 増やす
  • count == k のとき、max < (i − start + 1) であれば max を i − start + 1 に更新する
• 最後に max を返す

ウィンドウの右端 i を1つずつ進めながら、奇数の個数が k を超えたら左端 start を右へずらして調整します。これにより、常に「奇数がk個以下」のウィンドウを維持でき、count がちょうど k になった時点でその長さを記録していきます。

C++での実装例

#include<iostream>
using namespace std;
int oddSubarrayMaxLength(int arr[], int n, int k) {
    int max_len = 0, count = 0, start = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 != 0)
            count++;
        while (count > k && start <= i)
            if (arr[start++] % 2 != 0)
                count--;
        if (count == k)
            if (max_len < (i - start + 1))
                max_len = i - start + 1;
    }
    return max_len;
}
int main() {
    int arr[] = {2, 3, 4, 11, 4, 12, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 1;
    cout << "Maximum Length is: " << oddSubarrayMaxLength(arr, n, k);
}

実行結果

Maximum Length is: 4