数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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.
解决方案方法
为了解决这个问题，我们将以一种使它们的乘积之和最大化的方式找到对。为了使和最大化，我们需要将相同的值配对在一起。为了使配对更容易，我们需要对数组进行排序，然后将负数和正数配对。然后找到对中是否存在一个正数或负数或两者都存在。如果剩余一个正数/负数，则将其添加到对中，如果存在一个负数和一个正数，则添加它们的乘积。
算法
初始化 -
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
更新于: 2020-12-09
355 次查看
广告