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
猜你喜欢