JavaScriptで絶対差が指定した数以下となる最長の部分配列を求める方法

問題の概要

数値の配列（第1引数：arr）と数値（第2引数：num）を受け取るJavaScript関数を作成します。この関数は、配列内の任意の2つの要素間の絶対差がnum以下となる最長の部分配列（連続・非連続を問わない）の長さを求めて返す必要があります。

入力例と出力例

例えば、入力配列と数値が以下の通りだったとします。

const arr = [7, 9, 8, 6, 6, 3];
const num = 1;

この場合、期待される出力は次のようになります。

const output = 3;

これは、条件を満たす最長の部分配列が [7, 6, 6] であるためです。この部分配列内の要素同士の絶対差は、すべて1以下に収まっています。

実装コード

この問題を解くコードは以下の通りです。

const arr = [7, 9, 8, 6, 6, 3];
const maximumSubarray = (arr = [], num = 1) => {
    if(!arr.length){
        return 0;
    };
    const maximum = arr.reduce((acc, val) => Math.max(acc, val));
    const buckets = new Array(maximum + 1);
    buckets.fill(0);
    const { length } = arr;
    for(let i=0; i< length; i++){
        buckets[arr[i]] += num;
    };
    let max = 0;
    for(let j=1; j< maximum + 1; j++) {
        let curr = buckets[j];
        let prev = buckets[j - 1];
        if(prev != 0 && prev + curr > max) {
            max = prev + curr;
        };
    };
    return max;
};
console.log(maximumSubarray(arr));

コードの解説

この実装では、バケット（bucket）方式を用いています。処理の流れは以下の通りです。

まず、配列が空の場合は0を返します。次に、reduceメソッドを使って配列内の最大値を求め、その値+1のサイズを持つバケット配列を用意して0で初期化します。その後、各要素を対応するバケットに記録していきます。最後に、隣接するバケット同士の値を順番に比較し、合計が最大となる組み合わせを探すことで、条件を満たす最長の長さを算出しています。

このアプローチにより、要素同士の絶対差がnum以下となる要素を効率的に数え上げることができます。

実行結果

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

3