【C++入門】2つの配列の積の最大合計を求めるアルゴリズムと実装例

はじめに

本記事では、2つの配列の積の最大合計（Maximum Sum of Products）をC++で求めるプログラムについて解説します。

この問題では、同じサイズを持つ2つの配列が与えられます。私たちのタスクは、一方の配列の要素ともう一方の配列の要素を1対1で掛け合わせ、その積の総和が最大になるような組み合わせを見つけることです。

解き方のアプローチ：貪欲法

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。考え方はシンプルです。

• まず、両方の配列をそれぞれ昇順にソートします。
• 次に、小さい値同士・大きい値同士を対応付けて掛け合わせます。
• 負の数が含まれる場合でも、「マイナス × マイナス ＝ プラス」となるため、この対応付けが常に最適な結果をもたらします。

C++によるサンプルコード

#include<bits/stdc++.h>
using namespace std;

// ソートした配列同士を対応付けて
// 積の最大合計を計算する関数
int maximumSOP(int a[], int b[], int n) {
   int sop = 0;
   sort(a, a + n);
   sort(b, b + n);
   for (int i = 0; i < n; i++) {
      sop += a[i] * b[i];
   }
   return sop;
}

int main() {
   int A[] = { 1, 2, 3 };
   int B[] = { 4, 5, 1 };
   int n = sizeof(A) / sizeof(A[0]);
   cout<<maximumSOP(A, B, n);
   return 0;
}

実行結果

24

コードの解説

maximumSOP 関数では、引数として受け取った2つの配列 a と b を、標準ライブラリの sort() を使って昇順に並べ替えています。その後、インデックスが同じ位置にある要素同士を掛け合わせ、変数 sop に加算していきます。

サンプルでは、配列 A = {1, 2, 3} と B = {4, 5, 1} をソートすると、それぞれ {1, 2, 3} と {1, 4, 5} になります。これらを対応付けて計算すると、

1×1 + 2×4 + 3×5 = 1 + 8 + 15 = 24

となり、最大合計は 24 であることが分かります。

なお、配列のサイズ n は main() 側で sizeof(A) / sizeof(A[0]) によって正しく求め、関数へ明示的に渡すのが安全です。関数の引数として渡されたポインタに対して直接 sizeof を使うと、配列全体のサイズではなくポインタのサイズが返されてしまう点に注意しましょう。

計算量

ソート処理がボトルネックとなるため、このアルゴリズムの時間計算量は O(n log n) です。要素数が増えても高速に動作する、非常に効率的な手法といえます。