C++で配列内の最長の連続する偶数の個数を求める方法

要素数 n の配列 A が与えられたとき、その中に含まれる「連続した偶数」の最大個数を求める問題を考えてみましょう。例えば、配列が A = [1, 2, 3, 4, 6, 8, 7] の場合、4・6・8 と偶数が3つ続いているため、答えは 3 となります。

アルゴリズムの考え方

この問題は非常にシンプルな方法で解くことができます。ポイントは2つのカウント変数を用意することです。

• max_current: 現在進行中の連続する偶数の個数
• max_till_now: これまでに見つかった最大の連続偶数の個数

配列を先頭から順に走査し、偶数を見つけたら max_current を1増やして、max_till_now と比較して大きい方を更新します。奇数が出現した時点で連続が途切れるため、max_current を 0 にリセットします。

実装例(C++)

#include<iostream>
using namespace std;
int maxEvenContiguous(int arr[], int n) {
    int max_current = 0, max_till_now = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 != 0)
            max_current = 0;
        else {
            max_current++;
            max_till_now = max(max_current, max_till_now);
        }
    }
    return max_till_now;
}
int main() {
    int arr[] = {1, 2, 3, 4, 6, 8, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Max contiguous even number count: " << maxEvenContiguous(arr, n);
}

実行結果

Max contiguous even number count: 3

計算量について

このアルゴリズムは配列を一度だけ走査すればよいため、時間計算量は O(n)、使用する変数も定数個のみなので空間計算量は O(1) となります。大きな配列に対しても効率的に動作するのが特徴です。