C++で合計が偶数となる最大長の部分配列を求める方法

整数型の配列 Arr[] が与えられたとき、要素の合計が偶数となる最長の部分配列の長さを求めるのが本記事の目的です。つまり、部分配列内の要素をすべて足した値が偶数になり、かつその長さが最大となる部分配列を探します。

入力例と出力例

入力 − Arr[] = { 2, 3, 5, 2, 6, 7 }

出力 − 部分配列の最大長：4

説明 − 最大長の部分配列は { 5, 2, 6, 7 } です。合計は 20 となり、偶数になります。

入力 − Arr[] = { 5, 7, 7, 3, 4 }

出力 − 部分配列の最大長：4

説明 − 最大長の部分配列は { 5, 7, 7, 3 } です。合計は 22 となり、偶数になります。

アルゴリズムの考え方

• 整数を格納するために整数型配列 Arr[] を使用します。
• 変数 size には配列の長さを格納します。
• 関数 Length(int arr[]) は配列の合計が偶数であるかどうかを判定します。変数 leng は部分配列の長さを保持します。
• まず配列全体の合計を計算し、それが偶数であれば配列の長さ n をそのまま返します。
• 合計が奇数の場合は、少なくとも1つの奇数要素を除外する必要があります。そこで先頭の要素から順に配列を走査し、奇数の要素 arr[i] が見つかったら、その要素を含まない左側と右側それぞれの部分配列の長さを求めます。
• 最後に、求めた長さの中で最大のものを部分配列の長さとして返します。

この方法のポイントは、配列全体の合計が奇数のとき、奇数要素を1つ取り除けば必ず合計が偶数になるという性質です。したがって、各奇数要素について「その要素より左側」または「その要素より右側」のどちらか長い方を採用すればよいことになります。計算量は O(n) と効率的です。

サンプルコード

#include <iostream>
int Length(int arr[], int n){
    int sum = 0, leng = 0;
    // 配列全体の合計が偶数の場合
    for (int i = 0; i < n; i++)
        sum += arr[i];
    if (sum % 2 == 0) // 合計がすでに偶数
        return n;
    // 奇数となる要素 a[i] のインデックス i を探し、
    // a[i] を除外した左右それぞれの長さを比較して
    // 最大長の部分配列を求める
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 1)
            leng = i > n - i - 1 ? i : n - i - 1;
    }
    return leng;
}
int main(){
    int Arr[] = { 1, 2, 6, 2, 4, 2 };
    int size = 6;
    printf("Maximum length of subarray such that sum of the subarray is even: %d", Length(Arr, size));
    return 0;
}

出力結果

上記のコードを実行すると、次のような出力が得られます −

Maximum length of subarray such that sum of the subarray is even : 5