Given an array of n elements. Find maximum sum of pairwise multiplications. Sum can be larger so take mod with 10^9+7. If there are odd elements, then we can add any one element (without forming a pair) to the sum.
Examples:
Input : arr[] = {-1, 4, 5, -7, -4, 9, 0}
Output : 77
So to get the maximum sum, the arrangement will
be {-7, -4}, {-1, 0}, {9, 5} and {4}.
So the answer is (-7*(-4))+((-1)*0)+(9*5)+(4) ={77}.
Input : arr[] = {8, 7, 9}
Output : 79
Answer is (9*8) +(7) = 79.
Approach:
- Sort the given array.
- First, multiply the negative numbers pairwise from the starting and add to the total_sum.
- Second, multiply the positive numbers pairwise from the last and to the total_sum.
- Check if negative and positive both counts are odd, then add the product of last pair
i.e. last negative and positive left. - Or if any of the one counts is odd, then add that element left.
- Return sum.
Implementation:
C++
// C++ program for above implementation#include <bits/stdc++.h>#define Mod 1000000007using namespace std;// Function to find the maximum sumlong long int findSum(int arr[], int n){ long long int sum = 0; // Sort the array first sort(arr, arr + n); // First multiply negative numbers pairwise // and sum up from starting as to get maximum // sum. 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; } // Second multiply positive numbers pairwise // and summed up from the last as to get maximum // sum. 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; } // To handle case if positive and negative // numbers both are odd in counts. if (j > i) sum = (sum + (arr[i] * arr[j]) % Mod) % Mod; // If one of them occurs odd times else if (i == j) sum = (sum + arr[i]) % Mod; return sum;}// Drivers codeint main(){ int arr[] = { -1, 9, 4, 5, -4, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findSum(arr, n); return 0;} |
Java
// Java program for above implementationimport java.io.*;import java.util.*;class GFG {static int Mod = 1000000007;// Function to find the maximum sumstatic long findSum(int arr[], int n) { long sum = 0; // Sort the array first Arrays.sort(arr); // First multiply negative numbers // pairwise and sum up from starting // as to get maximum sum. 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; } // Second multiply positive numbers // pairwise and summed up from the // last as to get maximum sum. 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; } // To handle case if positive and negative // numbers both are odd in counts. if (j > i) sum = (sum + (arr[i] * arr[j]) % Mod) % Mod; // If one of them occurs odd times else if (i == j) sum = (sum + arr[i]) % Mod; return sum;}// Drivers codepublic static void main(String args[]) { int arr[] = {-1, 9, 4, 5, -4, 7}; int n = arr.length; System.out.println(findSum(arr, n));}}/*This code is contributed by Nikita Tiwari.*/ |
Python3
# Python3 code for above implementationMod= 1000000007# Function to find the maximum sumdef findSum(arr, n): sum = 0 # Sort the array first arr.sort() # First multiply negative numbers # pairwise and sum up from starting # as to get maximum sum. i = 0 while i < n and arr[i] < 0: if i != n - 1 and arr[i + 1] <= 0: sum = (sum + (arr[i] * arr[i + 1]) % Mod) % Mod i += 2 else: break # Second multiply positive numbers # pairwise and summed up from the # last as to get maximum sum. j = n - 1 while j >= 0 and arr[j] > 0: if j != 0 and arr[j - 1] > 0: sum = (sum + (arr[j] * arr[j - 1]) % Mod) % Mod j -= 2 else: break # To handle case if positive # and negative numbers both # are odd in counts. if j > i: sum = (sum + (arr[i] * arr[j]) % Mod) % Mod # If one of them occurs odd times elif i == j: sum = (sum + arr[i]) % Mod return sum# Driver codearr = [ -1, 9, 4, 5, -4, 7 ]n = len(arr) print(findSum(arr, n))# This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program for above implementationusing System;class GFG { static int Mod = 1000000007; // Function to find the maximum sum static long findSum(int[] arr, int n) { long sum = 0; // Sort the array first Array.Sort(arr); // First multiply negative numbers // pairwise and sum up from starting // as to get maximum sum. 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; } // Second multiply positive numbers // pairwise and summed up from the // last as to get maximum sum. 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; } // To handle case if positive and negative // numbers both are odd in counts. if (j > i) sum = (sum + (arr[i] * arr[j]) % Mod) % Mod; // If one of them occurs odd times else if (i == j) sum = (sum + arr[i]) % Mod; return sum; } // Drivers code public static void Main() { int[] arr = { -1, 9, 4, 5, -4, 7 }; int n = arr.Length; Console.WriteLine(findSum(arr, n)); }}/*This code is contributed by vt_m.*/ |
PHP
<?php// PHP program for above implementation$Mod = 1000000007;// Function to find the maximum sumfunction findSum(&$arr, $n){ global $Mod; $sum = 0; // Sort the array first sort($arr); // First multiply negative numbers // pairwise and sum up from starting // as to get maximum sum. $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; } // Second multiply positive numbers pairwise // and summed up from the last as to get // maximum sum. $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; } // To handle case if positive and negative // numbers both are odd in counts. if ($j > $i) $sum = ($sum + ($arr[$i] * $arr[$j]) % $Mod) % $Mod; // If one of them occurs odd times else if ($i == $j) $sum = ($sum + $arr[$i]) % Mod; return $sum;}// Driver code$arr = array (-1, 9, 4, 5, -4, 7 );$n = sizeof($arr);echo findSum($arr, $n);// This code is contributed by ita_c?> |
Javascript
<script>// JavaScript program for above implementation let Mod = 1000000007; // Function to find the maximum sumfunction findSum(arr, n) { let sum = 0; // Sort the array first arr.sort(); // First multiply negative numbers // pairwise and sum up from starting // as to get maximum sum. let 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; } // Second multiply positive numbers // pairwise and summed up from the // last as to get maximum sum. let 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; } // To handle case if positive and negative // numbers both are odd in counts. if (j > i) sum = (sum + (arr[i] * arr[j]) % Mod) % Mod; // If one of them occurs odd times else if (i == j) sum = (sum + arr[i]) % Mod; return sum;}// Driver code let arr = [-1, 9, 4, 5, -4, 7]; let n = arr.length; document.write(findSum(arr, n)); </script> |
Output
87
Time Complexity : O(N log(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More here on that Topic: geeksforgeeks.org/maximum-sum-of-pairwise-product-in-an-array-with-negative-allowed/ […]
… [Trackback]
[…] Find More here to that Topic: geeksforgeeks.org/maximum-sum-of-pairwise-product-in-an-array-with-negative-allowed/ […]