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