C++で負の数を含む配列のペアワイズ積の最大合計を求めるアルゴリズム

はじめに

このチュートリアルでは、負の数を含む配列において、要素をペアにして積を計算した際の合計の最大値を求めるプログラムをC++で解説します。

整数の配列が与えられたとき、任意の2つの要素をペアとして掛け合わせ、すべてのペアの積の総和が最大になるような組み合わせを見つけるのが課題です。

アルゴリズムのポイント

最大の合計を得るためには、次のような貪欲法（グリーディ法）の戦略が有効です。

• 負の数同士をペアにする：負 × 負 ＝ 正 になるため、絶対値の大きい負の数同士（昇順ソート時の先頭側）から2つずつペアにすると、大きな正の値が得られます。
• 正の数同士をペアにする：大きい値同士を掛けるほど合計が大きくなるため、昇順ソート時の末尾側から2つずつペアにします。
• 余りが出た場合の処理：1つの負の数と1つの正の数が残った場合はそれらを掛け合わせ、要素が1つだけ残った場合はその値をそのまま合計に加算します。

C++での実装例

#include <bits/stdc++.h>
#define Mod 1000000007
using namespace std;
// 最大合計を求める関数
long long int findSum(int arr[], int n) {
    long long int sum = 0;
    // 配列を昇順にソート
    sort(arr, arr + n);
    int i = 0;
    // 負の数を先頭から2つずつペアにする
    while (i < n && arr[i] < 0) {
        if (i != n - 1 && arr[i + 1] <= 0) {
            sum = (sum + (arr[i] * arr[i + 1]) % Mod) % Mod;
            i += 2;
        }
        else
            break;
    }
    int j = n - 1;
    // 正の数を末尾から2つずつペアにする
    while (j >= 0 && arr[j] > 0) {
        if (j != 0 && arr[j - 1] > 0) {
            sum = (sum + (arr[j] * arr[j - 1]) % Mod) % Mod;
            j -= 2;
        }
        else
            break;
    }
    // 残った要素の処理
    if (j > i)
        sum = (sum + (arr[i] * arr[j]) % Mod) % Mod;
    else if (i == j)
        sum = (sum + arr[i]) % Mod;
    return sum;
}
int main() {
    int arr[] = { -1, 9, 4, 5, -4, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSum(arr, n);
    return 0;
}

出力結果

87

計算過程の解説

入力配列 { -1, 9, 4, 5, -4, 7 } を昇順にソートすると { -4, -1, 4, 5, 7, 9 } となります。

• 負の数のペア：（-4）×（-1）＝ 4
• 正の数のペア：9 × 7 ＝ 63、5 × 4 ＝ 20

これらを合計すると 4 + 63 + 20 = 87 となり、これが求める最大値です。

まとめ

本記事では、負の数を含む配列でペアワイズ積の合計を最大化する方法を紹介しました。配列をソートし、負の数は小さい方から、正の数は大きい方からペアリングするというシンプルな貪欲法により、効率よく最適解を求められます。計算量はソートに依存し、時間計算量は O(n log n) となります。