C ++程序中允许带负数的数组中成对乘积的最大和
在这个问题中，我们给了数组arr[]，其中包含n个整数值（允许使用负值）。我们的任务是创建一个程序，以查找允许为负的数组中成对乘积的最大和。
问题描述-我们需要使用数组的元素创建对，以使对的元素乘积之和最大。
让我们举个例子来了解这个问题，
输入项
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.
解决方法
为了解决该问题，我们将以使它们的乘积之和最大的方式来寻找对。为了使总和最大化，我们需要将相同的配对值配对在一起。为了使配对容易，我们需要对数组进行排序，然后将负片和正片配对。然后查找该对中是否存在一个正值或负值或两个值。如果保留正值/负值，则将其添加到该对中，如果存在一个负值和一个正值，则添加其乘积。
算法
初始化-
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<<"数组中成对乘积的最大和为 "<<calcSumPairProd(arr, n);
return 0;
}输出结果
数组中成对乘积的最大和为 104