Maximum sum of pairwise product in an array with negative allowed in C++

Question

---

In this tutorial, we will be discussing a program to find maximum sum of pairwise product in an array with negative allowed.

For this we will be provided with an array containing integers. Our task is to find the maximum sum while performing pairwise multiplications.

Example

 Live Demo

#include 
#define Mod 1000000007
using namespace std;
//finding the maximum sum
long long int findSum(int arr[], int n) {
   long long int sum = 0;
   //sorting the array
   sort(arr, arr + n);
   int i = 0;
   while (i < n && arr[i] < 0) {
      if (i != n - 1 && arr[i + 1] <= 0) {
         sum = (sum + (arr[i] * arr[i + 1]) % Mod) % Mod;
         i += 2;
      }
      else
         break;
   }
   int j = n - 1;
   while (j >= 0 && arr[j] > 0) {
      if (j != 0 && arr[j - 1] > 0) {
         sum = (sum + (arr[j] * arr[j - 1]) % Mod) % Mod;
         j -= 2;
      }
      else
         break;
   }
   if (j > i)
      sum = (sum + (arr[i] * arr[j]) % Mod) % Mod;
   else if (i == j)
      sum = (sum + arr[i]) % Mod;
   return sum;
}
int main() {
   int arr[] = { -1, 9, 4, 5, -4, 7 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << findSum(arr, n);
   return 0;
}

Output

87

Ayush Gupta

Published on 09-Sep-2020 13:16:30