C++プログラムで許可されている負の配列のペアワイズ積の最大合計

この問題では、n個の整数値（負の値を許可）を含む配列arr[]が与えられます。私たちのタスクは、負の値が許可された配列内のペアワイズ積の最大合計を見つけるプログラムを作成することです。

問題の説明 −ペアの要素の積の合計が最大になるように、配列の要素を使用してペアを作成する必要があります。

問題を理解するために例を見てみましょう

入力

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

出力

104

説明

The pairs to be considered: (−5, −3), (2, 3), (−1, 1), (7, 12)
Sum of product = (−5 * −3) + (2 * 3) + (−1 * 1) + (7 * 12) = 15 + 6 − 1 + 84 =
104.

ソリューションアプローチ

この問題を解決するために、それらの積の合計が最大になるようにペアを見つけます。合計を最大化するには、同じペアの値をペアにする必要があります。そして、このペアリングを簡単にするために、アレイをソートしてから、ネガティブとポジティブをペアリングする必要があります。次に、一方の正または負、あるいは両方の値がペアに存在するかどうかを確認します。正/負の値が残っている場合はそれをペアに追加し、1つの負の値と1つの正の値が存在する場合は、それらの積を追加します。

アルゴリズム

初期化 −

maxSum = 0.

ステップ1 −

Sort the array arr[].

ステップ2 −

Loop for all negative values of the array. Make pairs, and add their
product to maxSum.

ステップ3 −

Loop for all positive values of the array. Make pairs, and add their
product to maxSum.

ステップ4 −

At last check the remaining values.

ステップ4.1 −

If one positive value remains, add it to maxSum.

ステップ4.1 −

If one negative value remains, add it to maxSum.

ステップ4.1 −

If one positive value and one negative value remains, add
their product to maxSum.

ステップ5 −

Return maxSum.

例

ソリューションの動作を説明するプログラム

#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<<"The maximum sum of pairwise product in an array is "<<calcSumPairProd(arr, n);
   return 0;
}

出力

The maximum sum of pairwise product in an array is 104