JavaScriptで配列の中から最長の減少列（連続する部分列）の長さを求める方法

本記事では、整数の配列を受け取り、その中に含まれる最も長い減少列（連続する要素の並び）の長さを返すJavaScript関数の実装方法を解説します。減少列とは、隣り合う要素がそれまでの要素より大きくならずに、連続して減っていく部分列のことです。

問題の概要

たとえば、次のような入力配列が与えられたとします。

const arr = [5, 2, 5, 4, 3, 2, 4, 6, 7];

この場合、期待される出力は次のとおりです。

const output = 4;

これは、配列内で最も長く連続して減少している列が [5, 4, 3, 2] であり、その長さが 4 であるためです。

実装コード

const arr = [5, 2, 5, 4, 3, 2, 4, 6, 7];
const decreasingSequence = (arr = []) => {
    let longest = [];
    let curr = [];
    const setDefault = (newItem) => {
        if (curr.length > longest.length) {
            longest = curr;
        }
        curr = [newItem];
    };
    for (const item of arr) {
        if (curr.length && item > curr[curr.length - 1]) {
            setDefault(item);
        } else {
            curr.push(item);
        }
    }
    setDefault();
    return longest.length;
};
console.log(decreasingSequence(arr));

コードの解説

このアルゴリズムは、配列を一度だけ走査すればよいため、計算量は O(n) で非常に効率的です。処理の流れは以下のとおりです。

• longest: これまでに見つかった最長の減少列を保持する変数です。
• curr: 現在走査中の減少列を一時的に保持する変数です。
• setDefault(): 列をリセットする前に呼び出されるヘルパー関数です。現在の列 curr がこれまでの最長 longest より長ければ更新し、その後 curr を新しい要素で初期化します。
• メインの for...of ループでは、各要素が直前の要素より大きいかどうかを判定します。大きければ減少がそこで途切れたことを意味するため setDefault(item) を呼び出して新しい列を開始し、そうでなければ curr に要素を追加して減少列を伸ばします。
• ループ終了後にもう一度 setDefault() を呼び出すことで、末尾まで続いた減少列も確実に比較・反映されます。

出力

上記のコードを実行すると、コンソールには次の結果が出力されます。

4

このように、シンプルな線形走査と状態管理を組み合わせるだけで、最長の減少列を効率よく検出できます。同様のロジックは、「増加列」を求める場合にも判定条件を反転させるだけで応用可能です。