JavaScriptで2つの配列の積の最大合計を効率的に求める方法

本記事では、正の整数からなる2つの配列 arr1 と arr2 を扱います。両方の配列には同数の要素が含まれており、これらの配列を使って「要素同士の積の合計」が最大になる組み合わせを見つける関数を作成します。

問題の概要

arr1 の各要素は、arr2 のいずれか1つの要素と必ず1回だけ掛け合わせる必要があります。逆も同様で、両方の配列のすべての要素がちょうど1回ずつ使われ、その結果生じる積の合計が最大となるようにしなければなりません。

例えば、次のような配列が与えられたとしましょう。

arr1 = [5,1,3,4,2] および
arr2 = [8,10,9,7,6]

この場合、積の合計として考えられる例の一つが以下です。

5*6 + 1*7 + 3*9 + 4*10 + 2*8

しかし、これは必ずしも最大の合計ではありません。

解法のアプローチ：貪欲法（ソートして対応付け）

この問題を解く鍵となるのは、大きい数同士を掛け合わせると合計が最大化されるという性質です。これは貪欲法（Greedy Algorithm）に基づく考え方です。

具体的な手順は以下の通りです。

1. まず、両方の配列の長さが一致しているかどうかを確認します。一致していなければ処理を中断します。
2. 元の配列を変更しないよう、slice() でコピーを作成した上で、両方の配列を降順にソートします。
3. ソート後の配列の同じインデックスにある要素同士を掛け合わせ、その結果を順番に加算していきます。
4. 最終的な合計値を返します。

この方法により、各要素が1回だけ使用され、かつ積の合計が最大になる組み合わせが保証されます。

実装コード

以下が実際のコード例です。

const arr1 = [5,1,3,4,2];
const arr2 = [8,10,9,7,6];

// 降順に並べ替えるための比較関数
const sorter = (a, b) => b - a;

const greatestProduct = (a1, a2) => {
    // 配列の長さが異なる場合は false を返す
    if(a1.length !== a2.length){
        return false;
    };
    // 元の配列を壊さないようコピーしてから降順ソート
    const a1Sorted = a1.slice().sort(sorter);
    const a2Sorted = a2.slice().sort(sorter);
    
    let res = 0;
    for(let i = 0; i < a1.length; i++){
        res += (a1Sorted[i] * a2Sorted[i]);
    };
    return res;
};

console.log(greatestProduct(arr1, arr2));

実行結果

コンソールに出力される結果は以下の通りです。

130

計算の内訳

降順ソート後の配列はそれぞれ [5,4,3,2,1] と [10,9,8,7,6] になります。対応する要素同士を掛けると以下の計算になります。

5*10 + 4*9 + 3*8 + 2*7 + 1*6 = 50 + 36 + 24 + 14 + 6 = 130

まとめ

このアルゴリズムの時間計算量は、ソート処理が支配的であるため O(n log n) です。空間計算量については、コピーした配列分が必要となるため O(n) となります。貪欲法の典型的な応用例として、ソートによる対応付けが最適解を導くことを示す良いサンプルと言えるでしょう。