在这个问题中,我们给了数组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