【JavaScript】厳密に増加する要素のみを含む最長の連続部分配列の長さを求める方法

本記事では、数値の配列を唯一の引数として受け取る JavaScript 関数を作成する方法を解説します。この関数は、配列の中から「厳密に増加する（strictly increasing）」要素のみで構成される最長の連続部分配列を見つけ、その長さを返すものです。

厳密に増加する列とは？

「厳密に増加する列」とは、どの要素もその直前の要素よりも必ず大きい（等しい場合は不可）ような数列のことです。たとえば [5, 7, 8, 12] は各要素が前の要素より大きいため厳密に増加していますが、[4, 4, 6] は同じ値が連続しているため該当しません。

アルゴリズムの考え方

この問題は、配列を一度だけ走査する線形時間 O(n) のアプローチで解くことができます。手順は以下の通りです。

1. 現在の増加シーケンスの長さを記録するカウンタ count と、これまでの最大長 max を用意します。
2. 隣り合う要素を比較し、現在の要素が前の要素より大きければ count を増やします。
3. 大きくなければ増加が途切れたため、count を 0 にリセットします。
4. 各ステップで count が max を上回ったら更新します。

最終的に max + 1 を返すことで、実際の要素数（長さ）が求まります。これはカウントしているのが「隣接ペアの数」であり、要素数はそれより 1 多くなるためです。また、空の配列が渡された場合は 0 を返すようにガード節を設けています。

コード例

const arr = [5, 7, 8, 12, 4, 56, 6, 54, 89];

const findLongest = (arr) => {
    // 配列が空の場合は 0 を返す
    if(arr.length == 0) {
        return 0;
    };
    let max = 0;
    let count = 0;
    // 隣接する要素同士を比較しながら走査
    for(let i = 1; i < arr.length; i++) {
        if(arr[i] > arr[i-1]) {
            count++;
        } else {
            count = 0;
        }
        if(count > max) {
            max = count;
        }
    }
    return max + 1;
};

console.log(findLongest(arr));

出力結果

コンソールには以下のように表示されます。

4

処理の流れを確認

サンプル配列 [5, 7, 8, 12, 4, 56, 6, 54, 89] の場合を考えてみましょう。

・冒頭の 5, 7, 8, 12 は厳密に増加しているため、ここが最長のシーケンス（長さ 4）となります。
・次の 4 で増加が途切れるためカウントがリセットされます。
・その後の 56 や 54, 89 の部分はいずれも長さ 2 未満のため、最大値は更新されません。

したがって、結果として最も長い厳密に増加する連続部分配列の長さである「4」が出力されます。

まとめ

この実装では配列を 1 回走査するだけで済むため、計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。配列の要素数が大きくなっても高速に動作するため、実務でも安心して利用できるアプローチと言えます。