JavaScriptで「要素の合計＋インデックスの差」が最大となるペアを求める方法

問題

整数の配列 arr を唯一の引数として受け取る JavaScript 関数を作成します。

関数は、配列内のすべてのインデックスペアの中で (arr[i] + arr[j]) + (i − j) の値が最も大きくなるようなペア (i, j) を選び、その最大値を返す必要があります。

入力例

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

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

const output = 11;

出力の説明

i = 0、j = 2 を選んだ場合、計算は以下のようになります。

(8 + 5) + (0 - 2) = 11

これは、他のどのインデックスペアを選んでも達成できない最大値となっています。

解法のポイント

この式は次のように変形できます。

(arr[i] + i) + (arr[j] - j)

つまり、「より小さいインデックス側の arr[i] + i の最大値」を変数に記憶しながら配列を一度だけ走査し、各位置 j で「max(arr[i] + i) + arr[j] − j」を計算すれば答えが求まります。この方法なら、全ペアを調べる O(n²) の二重ループを避け、O(n) の時間計算量・O(1) の追加メモリで効率的に解くことができます。

コード例

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

const findMaximum = (arr = []) => {
    let max = arr[0] + 0;
    let res = -Infinity;
    for(let i = 1; i < arr.length; i++){
        res = Math.max(res, max + arr[i] - i);
        max = Math.max(arr[i] + i, max);
    };
    return res;
};
console.log(findMaximum(arr));

出力

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

11