Maximize sum of product and difference between any pair of array elements possible
Given an array arr[] of size N, the task is to find the maximum value of arr[i] ∗ arr[j] + arr[i] − arr[j] for any pair (arr[i], arr[j]) from the given array, where i != j and 0 < i, j < N – 1.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: 21
Explanation:
Among all the pairs of the array, the maximum value is obtained for the pair (arr[4], arr[3]), which is equal to
=> arr[4] * arr[3] + arr[4] – arr[3] = 5 * 4 + 5 – 4 = 20 + 1 = 21.Input: {-4, -5, 0, 1, 3}
Output: 21
Explanation:
Among all the pairs of the array, the maximum value is obtained for the pair (arr[0], arr[1]), which is equal to
=> arr[0] * arr[1] + arr[0] – arr[1] = (-4) * (-5) + (-4) – (-5) = 20 + 1 = 21.
Naive Approach: The simplest approach to solve the problem is to traverse the array and generate all possible pairs (arr[i], arr[j]) (i != j) from the array and evaluate the expression for all the pairs. Finally, print the maximum of all the pairs.
Below is the implementation of the approach:
C++
// C++ code for the approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum value of arr[i] * arr[j] + arr[i] - arr[j] int maxProductSum( int arr[], int N) { int maxSum = INT_MIN; // Generate all possible pairs (arr[i], arr[j]) for ( int i = 0; i < N - 1; i++) { for ( int j = i + 1; j < N; j++) { // Evaluate the expression for each pair // consider two permutation of pair for any 2 particular elements int sum1 = (arr[i] * arr[j]) + (arr[i] - arr[j]); int sum2 = (arr[j] * arr[i]) + (arr[j] - arr[i]); // taking maximum expression value among two permutations int sum = max(sum1, sum2); // Update the maximum value maxSum = max(maxSum, sum); } } // Return the maximum value return maxSum; } // Driver code int main() { int arr[] = { -4, -5, 0, 1, 3 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call to find the maximum value int maxSum = maxProductSum(arr, N); // Print the maximum value cout << maxSum << endl; return 0; } |
Java
// Java code for the approach import java.util.*; public class GFG { // Function to find the maximum value of arr[i] * arr[j] // + arr[i] - arr[j] static int maxProductSum( int [] arr, int N) { int maxSum = Integer.MIN_VALUE; // Generate all possible pairs (arr[i], arr[j]) for ( int i = 0 ; i < N - 1 ; i++) { for ( int j = i + 1 ; j < N; j++) { // Evaluate the expression for each pair // consider two permutation of pair for any // 2 particular elements int sum1 = (arr[i] * arr[j]) + (arr[i] - arr[j]); int sum2 = (arr[j] * arr[i]) + (arr[j] - arr[i]); // taking maximum expression value among two // permutations int sum = Math.max(sum1, sum2); // Update the maximum value maxSum = Math.max(maxSum, sum); } } // Return the maximum value return maxSum; } // Driver code public static void main(String[] args) { int [] arr = { - 4 , - 5 , 0 , 1 , 3 }; int N = arr.length; // Function call to find the maximum value int maxSum = maxProductSum(arr, N); // Print the maximum value System.out.println(maxSum); } } |
Python3
# Python3 code for the approach import sys # Function to find the maximum value of arr[i] * arr[j] + arr[i] - arr[j] def maxProductSum(arr, N): maxSum = - sys.maxsize # Generate all possible pairs (arr[i], arr[j]) for i in range (N - 1 ): for j in range (i + 1 , N): # Evaluate the expression for each pair sum1 = (arr[i] * arr[j]) + (arr[i] - arr[j]) sum2 = (arr[j] * arr[i]) + (arr[j] - arr[i]) # Taking maximum expression value among two permutations sum = max (sum1, sum2) # Update the maximum value maxSum = max (maxSum, sum ) # Return the maximum value return maxSum # Driver code if __name__ = = '__main__' : # Input array arr = [ - 4 , - 5 , 0 , 1 , 3 ] N = len (arr) # Function call to find the maximum value maxSum = maxProductSum(arr, N) # Print the maximum value print (maxSum) |
C#
using System; public class GFG { // Function to find the maximum value of arr[i] * arr[j] // + arr[i] - arr[j] static int MaxProductSum( int [] arr, int N) { int maxSum = int .MinValue; // Generate all possible pairs (arr[i], arr[j]) for ( int i = 0; i < N - 1; i++) { for ( int j = i + 1; j < N; j++) { // Evaluate the expression for each pair // consider two permutation of pair for any // 2 particular elements int sum1 = (arr[i] * arr[j]) + (arr[i] - arr[j]); int sum2 = (arr[j] * arr[i]) + (arr[j] - arr[i]); // taking maximum expression value among two // permutations int sum = Math.Max(sum1, sum2); // Update the maximum value maxSum = Math.Max(maxSum, sum); } } // Return the maximum value return maxSum; } // Driver code static void Main( string [] args) { int [] arr = { -4, -5, 0, 1, 3 }; int N = arr.Length; // Function call to find the maximum value int maxSum = MaxProductSum(arr, N); // Print the maximum value Console.WriteLine(maxSum); } } |
Javascript
// Function to find the maximum value of arr[i] * arr[j] + arr[i] - arr[j] function maxProductSum(arr, N) { let maxSum = -Infinity; // Generate all possible pairs (arr[i], arr[j]) for (let i = 0; i < N - 1; i++) { for (let j = i + 1; j < N; j++) { // Evaluate the expression for each pair const sum1 = arr[i] * arr[j] + arr[i] - arr[j]; const sum2 = arr[j] * arr[i] + arr[j] - arr[i]; // Taking maximum expression value among two permutations const sum = Math.max(sum1, sum2); // Update the maximum value maxSum = Math.max(maxSum, sum); } } // Return the maximum value return maxSum; } // Driver code const arr = [-4, -5, 0, 1, 3]; const N = arr.length; // Function call to find the maximum value const maxSum = maxProductSum(arr, N); // Print the maximum value console.log(maxSum); |
21
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The optimal idea is based on the observation that the value of the expression can be maximum for the following 2 cases:
- If the pair includes the largest and the second-largest array elements.
- If the pair includes one smallest and the second smallest array elements are selected. This may arise when the smallest and the second smallest elements are both negative and their product will result in a positive number.
Follow the steps below to solve the problem:
- Sort the array arr[] in ascending order.
- Evaluate the expression for the pair arr[N – 1] and arr[N – 2] and store it in a variable, say max1.
- Similarly, evaluate the expression for the pair arr[1] and arr[0] and store it in a variable, say max2.
- Store the maximum of max1 and max2 in a variable, say ans.
- Print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to evaluate given expression int compute( int a, int b) { // Store the result int ans = a * b + a - b; return ans; } // Function to find the maximum value of // the given expression possible for any // unique pair from the given array void findMaxValue( int arr[], int N) { // Sort the array in ascending order sort(arr, arr + N); // Evaluate the expression for // the two largest elements int maxm = compute(arr[N - 1], arr[N - 2]); // Evaluate the expression for // the two smallest elements maxm = max(maxm, compute(arr[1], arr[0])); // Print the maximum cout << maxm; } // Driver Code int main() { // Given array int arr[] = { -4, -5, 0, 1, 3 }; // Store the size of the array int N = sizeof (arr) / sizeof (arr[0]); findMaxValue(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to evaluate given expression static int compute( int a, int b) { // Store the result int ans = a * b + a - b; return ans; } // Function to find the maximum value of // the given expression possible for any // unique pair from the given array static void findMaxValue( int arr[], int N) { // Sort the array in ascending order Arrays.sort(arr); // Evaluate the expression for // the two largest elements int maxm = compute(arr[N - 1 ], arr[N - 2 ]); // Evaluate the expression for // the two smallest elements maxm = Math.max(maxm, compute(arr[ 1 ], arr[ 0 ])); // Print the maximum System.out.print(maxm); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { - 4 , - 5 , 0 , 1 , 3 }; // Store the size of the array int N = arr.length; findMaxValue(arr, N); } } // This code is contributed by saanjoy_62 |
Python3
# Python Program for the above approach # Function to evaluate given expression def compute(a, b): # Store the result res = (a * b) + (a - b) return res # Function to find the maximum value of # the given expression possible for any # unique pair from the given array def findMaxValue(arr, N): # Sort the list in ascending order arr.sort() # Evaluate the expression for # the two largest elements maxm = compute(arr[N - 1 ], arr[N - 2 ]) # Evaluate the expression for # the two smallest elements maxm = max (maxm, compute(arr[ 1 ], arr[ 0 ])); print (maxm) # Driver code # given list arr = [ - 4 , - 5 , 0 , 1 , 3 ] # store the size of the list N = len (arr) findMaxValue(arr, N) # This code is contributed by santhoshcharan. |
C#
// C# program for above approach using System; public class GFG { // Function to evaluate given expression static int compute( int a, int b) { // Store the result int ans = a * b + a - b; return ans; } // Function to find the maximum value of // the given expression possible for any // unique pair from the given array static void findMaxValue( int [] arr, int N) { // Sort the array in ascending order Array.Sort(arr); // Evaluate the expression for // the two largest elements int maxm = compute(arr[N - 1], arr[N - 2]); // Evaluate the expression for // the two smallest elements maxm = Math.Max(maxm, compute(arr[1], arr[0])); // Print the maximum Console.WriteLine(maxm); } // Driver code public static void Main(String[] args) { // Given array int [] arr = { -4, -5, 0, 1, 3 }; // Store the size of the array int N = arr.Length; findMaxValue(arr, N); } } // This code is contributed by susmitakundugoaldanga. |
Javascript
<script> // Javascript implementation of the above approach // Function to evaluate given expression function compute(a, b) { // Store the result var ans = a * b + a - b; return ans; } // Function to find the maximum value of // the given expression possible for any // unique pair from the given array function findMaxValue(arr, N) { // Sort the array in ascending order arr.sort( function (a,b){ return a - b}); // Evaluate the expression for // the two largest elements var maxm = compute(arr[N - 1], arr[N - 2]); // Evaluate the expression for // the two smallest elements maxm = Math.max(maxm, compute(arr[1], arr[0])); // Print the maximum document.write(maxm); } // Driver Code var arr = [-4, -5, 0, 1, 3]; var N = arr.length; findMaxValue(arr, N); // This code is contributed by Shubhamsingh10 </script> |
21
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Contact Us