C++で2つの配列の積の合計を最大化するプログラムの解説

この記事では、サイズnの2つの配列 arr1[] と arr2[] が与えられたとき、対応する要素同士の積の合計が最大になるように計算するC++プログラムを紹介します。

問題の概要

arr1 の1つの要素と arr2 の1つの要素を掛け合わせた積を、すべての要素について求め、その合計が最大になる組み合わせを見つけるのが目的です。

入力例

arr1[] = {3, 5, 6}
arr2[] = {1, 4, 2}

出力例

37

解説

積の最大合計：6×4 + 5×2 + 3×1 = 24 + 10 + 3 = 37

解法のアプローチ

最も単純な方法は、arr1 と arr2 のすべての要素ペアを列挙し、その中から最大の合計を探すことです。しかし、この方法は計算量が大きくなり非効率です。

より効率的なアプローチは、「大きい値同士を掛け合わせる」ことです。両方の配列を降順にソートすれば、それぞれの配列の大きな値が対応する位置に揃います。あとはインデックス0からn-1まで対応する要素同士を掛け合わせ、その合計を返すだけで最大値が得られます。

これは「大小関係を保ったままペアを作ると積の総和が最大化される」という性質（交換不等式）に基づいており、ソート1回分のコスト O(n log n) で最適解を求められます。

C++での実装例

以下は、この解法の動作を示すサンプルプログラムです。

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

int calcMaxSumOfProd(int arr1[], int arr2[], int n){
    int maxSum = 0;
    // 両方の配列を降順にソート
    sort(arr1, arr1 + n, greater<int>());
    sort(arr2, arr2 + n, greater<int>());
    // 対応する要素同士の積を合計
    for (int i = 0; i < n; i++)
        maxSum += (arr1[i] * arr2[i]);
    return maxSum;
}

int main() {
    int arr1[] = { 3, 5, 6 };
    int arr2[] = { 1, 4, 2 };
    int n = sizeof(arr1)/sizeof(arr1[0]);
    cout<<"2つの配列の積の最大合計は "<<calcMaxSumOfProd(arr1, arr2, n);
    return 0;
}

実行結果

2つの配列の積の最大合計は 37

まとめ

2つの配列の積の最大合計を求めるには、両方の配列を降順にソートしてから対応する要素同士を掛け合わせて合計するのが最も効率的です。全ペアを試す力任せの方法と比べ、計算量を大幅に抑えられるため、実務でも推奨されるアプローチです。