JavaScriptで2進数配列に含まれる連続する「1」の最大長を求める方法

問題の概要

JavaScriptで、0と1のみから構成されるバイナリ配列(2進数配列)を引数として受け取り、その中で「1」が連続している部分配列の最大の長さを返す関数を作成する必要があります。

例えば、入力配列が以下の場合を考えてみましょう。

const arr = [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1];

この場合、最も長く連続する「1」は4つあるため、出力は次のようになります。

const output = 4;

解決アプローチ:スライディングウィンドウ法

この問題はスライディングウィンドウ(尺取り法)というアルゴリズムを使うことで効率的に解けます。これは、「1」のみで構成される最も大きなウィンドウ(区間)を追跡していく手法です。

具体的には、左右2つのポインター(left と right)を用意し、right を配列の末尾まで進めながら、要素が 0 に出会ったタイミングで現在のウィンドウ幅を記録します。そして、これまでの最大値より大きければ更新していきます。配列全体を一度だけ走査すればよいため、計算量は O(n) と非常に効率的です。

実装コード

const arr = [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1];
const findMaxConsecutiveOnes = (arr = []) => {
    let left = 0;
    let right = 0;
    let max = 0;
    while (right < arr.length) {
        if (arr[right] === 0) {
            if (right - left > max) {
                max = right - left
            };
            right++;
            left = right;
        } else {
            right++
        };
    };
    return right - left > max ? right - left : max;
}
console.log(findMaxConsecutiveOnes(arr));

コードの解説

• left:現在調べている連続区間の開始位置を示すポインターです。
• right:配列を先頭から末尾へ走査するポインターです。
• max:これまでに見つかった連続する「1」の最大長を保持します。
• arr[right] が 0 のとき、直前までの区間の長さ(right - left)が max より大きければ更新し、left を新しい区間の先頭へ移動させます。
• ループ終了後、最後の連続区間の長さも考慮して最大値を返します。

出力結果

上記のコードをコンソールで実行すると、次の出力が得られます。

4

このように、スライディングウィンドウ法を活用することで、バイナリ配列内の連続する「1」の最大長を線形時間(O(n))で簡単かつ効率的に求めることができます。