Tổng tối đa của tích từng cặp trong một mảng có phép âm trong chương trình C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] chứa n giá trị nguyên (cho phép giá trị âm). Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng số tối đa của các sản phẩm ghép đôi trong một mảng có phép âm.

Mô tả sự cố - Chúng ta cần tạo các cặp bằng cách sử dụng các phần tử của mảng sao cho tổng tích các phần tử của các cặp là lớn nhất.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

arr[] = {−5, 2, 3, 7, −1, 1, −3, 12}

Đầu ra

104

Giải thích

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.

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta sẽ tìm các cặp sao cho tổng các tích của chúng là lớn nhất. Để tối đa hóa tổng, chúng ta cần ghép các giá trị ghép đôi giống nhau với nhau. Và làm cho việc ghép nối này trở nên dễ dàng, chúng ta cần sắp xếp mảng và sau đó ghép nối âm và dương. Sau đó, tìm xem có một giá trị âm hoặc âm dương hoặc cả hai giá trị có trong cặp hay không. Nếu còn lại một giá trị dương / âm, hãy thêm nó vào cặp và nếu có một giá trị âm và một giá trị dương thì hãy thêm sản phẩm của họ.

Thuật toán

Khởi tạo -

maxSum = 0.

Bước 1 -

Sort the array arr[].

Bước 2 -

Loop for all negative values of the array. Make pairs, and add their
product to maxSum.

Bước 3 -

Loop for all positive values of the array. Make pairs, and add their
product to maxSum.

Bước 4 -

At last check the remaining values.

Bước 4.1 -

If one positive value remains, add it to maxSum.

Bước 4.1 -

If one negative value remains, add it to maxSum.

Bước 4.1 -

If one positive value and one negative value remains, add
their product to maxSum.

Bước 5 -

Return maxSum.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

The maximum sum of pairwise product in an array is 104