JavaScriptで配列内の最長の「山」部分配列の長さを求める方法

山（マウンテン）部分配列とは

配列 arr の（連続した）部分配列 sub が「山」と呼ばれるのは、以下の性質を満たす場合です。

• sub.length >= 3 であること

• ある 0 < i < sub.length - 1 が存在し、sub[0] < sub[1] < ... < sub[i] > sub[i+1] > ... > sub[sub.length - 1] となること。つまり、一度増加していき頂点に達した後、減少に転じる形状を持つこと

問題

数値の配列 arr を第一引数（唯一の引数）として受け取るJavaScript関数を作成する必要があります。

この関数は、配列 arr 内に存在する最も長い「山」の部分配列の長さを返します。山がひとつも存在しない場合は 0 を返します。

例えば、関数への入力が次の場合を考えてみましょう。

入力

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

出力

const output = 5;

出力の説明

この入力に対して求められる部分配列は次のとおりです。

[2, 5, 8, 4, 3]

この部分配列は 2 → 5 → 8 と増加し、8 を頂点として 4 → 3 と減少するため、有効な「山」となります。

コード例

以下がその実装コードです。

const arr = [3, 2, 5, 8, 4, 3, 6];
const mountainLength = (arr = []) => {
    let max = 0
    for(let left = 0; left < arr.length; left++) {
        let right = left
        while(arr[right] < arr[right + 1]) {
            right++
        }
        const top = right
        while(right > left && arr[right] > arr[right + 1]) {
            right++
        }
        if(right > top && top > left) {
            max = Math.max(max, right - left + 1)
            left = right
            left--
        }
    }
    return max
}
console.log(mountainLength(arr));

出力

5

アルゴリズムの解説

このアプローチでは、各インデックスを「山の左端（ふもと）」として扱います。まず while ループで昇順に登り続け、頂点の位置を top として記録します。その後、降順に下れる限り right を進めます。

right が top より先に進んでおり（下降区間が存在）、かつ top が left より大きい（上昇区間が存在）場合のみ、有効な山とみなして最大長を更新します。また、探索済みの区間をスキップすることで無駄な比較を避けています。

この手法により、配列全体を一度走査するだけで結果が得られ、時間計算量は O(n)、空間計算量は O(1) という効率的な解法になります。