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

•  10-09-2020
•  |
•
War es hilfreich?

Frage

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 <bits/stdc++.h>
#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
Published on 09-Sep-2020 13:16:30

War es hilfreich?
Nicht verbunden mit Tutorialspoint