JavaScriptで配列内の要素間の最大差を求める方法（順序条件付きの効率的手法）

問題の概要

数値の配列を受け取るJavaScript関数を作成します。この関数は、配列内の要素同士の差のうち最大となるものを見つけ出す必要があります。

ただし、重要な条件が1つあります。それは「小さい方の要素は、元の配列において大きい方の要素より前に出現しなければならない」という制約です。

例

次のような数値の配列を考えてみましょう。

const arr = [2, 5, 6, 12, 1];

この配列に対して、関数は 10 を返す必要があります。

一見すると、配列の最大値と最小値はそれぞれ 12 と 1 なので、その差である 11 が答えに思えるかもしれません。しかし、1 は 12 よりも後ろに出現しているため、今回の条件では有効な「小さい数」としては扱えません。

したがって、関数が返すべき差は次のようになります。

12 - 2 = 10

解決策：コード例

以下が実際のコードです。この種の問題は、株式売買で利益を最大化する問題と同じ発想で解けます。配列を一度だけ走査しながら「それまでに出現した最小値」を記録し、現在の要素との差を随時更新していくアプローチです。

const arr = [2, 5, 6, 12, 1];
const findLargestDifference = (arr = []) => {
    if (arr.length <= 1){
        return -1;
    };
    let min = arr[0];
    let diff = 0;
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > min && (arr[i] - min > diff)) {
            diff = arr[i] - min;
        }
        else if (arr[i] <= min) {
            min = arr[i];
        }
    }
    if (diff <= 0){
        return -1
    };
    return diff;
};
console.log(findLargestDifference(arr));

コードの解説

• まず、配列の長さが 1 以下の場合は比較対象となるペアが存在しないため、-1 を返します。
• 変数 min には「これまでに見つかった最小値」を保持します。初期値として配列の先頭要素を代入しておきます。
• 変数 diff は、現時点で見つかっている最大の差を表します。
• ループ処理の中では、現在の要素が min より大きく、かつその差が既存の diff を上回る場合にのみ diff を更新します。
• 逆に、現在の要素が min 以下であれば、それを新しい最小値として更新します。こうすることで、常に「手前にある小さい要素」を基準に差を計算できるため、順序の条件が自然に満たされます。
• 最後に、正の差が一度も見つからなかった場合（diff <= 0）は -1 を返し、そうでなければ計算結果の diff を返します。

このアルゴリズムは配列をたった1回の走査で処理できるため、時間計算量は O(n)、追加のメモリ使用量は O(1) という非常に効率的な実装となっています。配列全体の最大値・最小値を別々に求めて差を計算する単純な方法と違い、要素の出現順序を考慮した点がポイントです。

出力結果

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

10