負の値を含む配列でペアワイズ積の最大合計を求めるC++プログラム

この問題では、n個の整数（負の値も許容）からなる配列 arr[] が与えられます。目的は、負の値が含まれる場合でも、要素ペアの積の合計が最大となるようにペアを作成するプログラムを作ることです。

問題の概要

配列の要素を用いてペアを作り、各ペアの積を足し合わせたときに合計が最大になるような組み合わせを見つける必要があります。

具体例で問題を確認しましょう。

入力

arr[] = {−5, 2, 3, 7, −1, 1, −3, 12}

出力

104

説明

選ぶペア：(−5, −3), (2, 3), (−1, 1), (7, 12)
積の合計 = (−5 × −3) + (2 × 3) + (−1 × 1) + (7 × 12)
        = 15 + 6 − 1 + 84 = 104

解法のアプローチ

積の合計を最大化するためには、「同じ符号の値同士」をペアにするのが有効です。負×負＝正、正×正＝正となるため、絶対値の大きい値同士を掛け合わせるほど合計が大きくなります。このペアリングを簡単に行うために、まず配列をソートし、負の値同士・正の値同士でそれぞれペアを作成します。その後、1つだけ余った正の値や負の値、あるいは正と負が1つずつ残った場合の処理を行います。

アルゴリズム

初期化：

maxSum = 0

ステップ1： 配列 arr[] をソートします。

ステップ2： 負の値に対してループを行い、ペアを作成してその積を maxSum に加算します。

ステップ3： 正の値に対してループを行い、ペアを作成してその積を maxSum に加算します。

ステップ4： 最後に残った値を確認します。

• 正の値が1つだけ残っている場合 → その値を maxSum に加算します。
• 負の値が1つだけ残っている場合 → その値を maxSum に加算します。
• 正の値と負の値が1つずつ残っている場合 → それらの積を maxSum に加算します。

ステップ5： maxSum を返します。

実装例

上記の解法を実装したC++プログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
long calcSumPairProd(int arr[], int n) {
    long maxSum = 0;
    sort(arr, arr + n);
    int i = 0, j = (n - 1);
    while (i < n && arr[i] < 0) {
        if (i != n - 1 && arr[i + 1] <= 0) {
            maxSum = (maxSum + (arr[i] * arr[i + 1]));
            i += 2;
        }
        else
        break;
    }
    while (j >= 0 && arr[j] > 0) {
        if (j != 0 && arr[j - 1] > 0) {
            maxSum = (maxSum + (arr[j] * arr[j - 1]));
            j -= 2;
        }
        else
        break;
    }
    if (j > i)
    maxSum = (maxSum + (arr[i] * arr[j]));
    else if (i == j)
    maxSum = (maxSum + arr[i]);
    return maxSum;
}
int main() {
    int arr[] = { -5, 2, 3, 7, -1, 1, -3, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"配列におけるペアワイズ積の最大合計 = "<<calcSumPairProd(arr, n);
    return 0;
}

出力

配列におけるペアワイズ積の最大合計 = 104