Maximum value of (arr[i] * arr[j]) + (arr[j] – arr[i])) possible for any pair in an array
Given an array arr[] consisting of N integers, the task is to find the maximum possible value of the expression (arr[i] * arr[j]) + (arr[j] – arr[i])) for any pair (i, j), such that i ? j and 0 ? (i, j) < N.
Examples:
Input: arr[] = {-2, -8, 0, 1, 2, 3, 4}
Output: 22
Explanation:
For the pair (-8, -2) the value of the expression (arr[i] * arr[j]) + (arr[j] – arr[i])) = ((-2)*(-8) + (-2 – (-8))) = 22, which is maximum among all possible pairs.Input: arr[] = {-47, 0, 12}
Output: 47
Naive Approach: The simplest approach to solve the given problem is to generate all possible pairs of the array and find the value of the given expression (arr[i] * arr[j]) + (arr[j] – arr[i])) for each pair and print the maximum value obtained for any pair.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized, which is based on the observation that the maximum value of the expression will be obtained by selecting the pairs of maximum and second maximum or a minimum and second minimum of the array. Follow the steps below to solve the problem:
- Initialize a variable, say ans, to store the resultant maximum value.
- Sort the array in ascending order.
- Find maximum and second maximum elements of the array, say X and Y respectively, and update the value of ans to the maximum of ans and the value of the expression with values X and Y.
- Find minimum and second minimum elements of the array, say X and Y respectively, and update the value of ans to the maximum of ans and the value of the expression with values X and Y.
- After completing the above steps, 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 find the value of // the expression a * b + (b - a) int calc( int a, int b) { return a * b + (b - a); } // Function to find the maximum value // of the expression a * b + (b - a) // possible for any pair (a, b) int findMaximum(vector< int > arr, int N) { // Sort the vector in ascending order sort(arr.begin(), arr.end()); // Stores the maximum value int ans = -1e9; // Update ans by choosing the pair // of the minimum and 2nd minimum ans = max(ans, calc(arr[0], arr[1])); // Update ans by choosing the pair // of maximum and 2nd maximum ans = max(ans, calc(arr[N - 2], arr[N - 1])); // Return the value of ans return ans; } // Driver Code int main() { vector< int > arr = { 0, -47, 12 }; int N = ( int )arr.size(); cout << findMaximum(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the value of // the expression a * b + (b - a) static int calc( int a, int b) { return a * b + (b - a); } // Function to find the maximum value // of the expression a * b + (b - a) // possible for any pair (a, b) static int findMaximum( int [] arr, int N) { // Sort the vector in ascending order Arrays.sort(arr); // Stores the maximum value int ans = ( int )-1e9; // Update ans by choosing the pair // of the minimum and 2nd minimum ans = Math.max(ans, calc(arr[ 0 ], arr[ 1 ])); // Update ans by choosing the pair // of maximum and 2nd maximum ans = Math.max(ans, calc(arr[N - 2 ], arr[N - 1 ])); // Return the value of ans return ans; } // Driver Code public static void main(String[] args) { // Given inputs int [] arr = { 0 , - 47 , 12 }; int N = arr.length; System.out.println(findMaximum(arr, N)); } } // This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function to find the value of # the expression a * b + (b - a) def calc(a, b): return a * b + (b - a) # Function to find the maximum value # of the expression a * b + (b - a) # possible for any pair (a, b) def findMaximum(arr, N): # Sort the vector in ascending order arr = sorted (arr) # Stores the maximum value ans = - 10 * * 9 # Update ans by choosing the pair # of the minimum and 2nd minimum ans = max (ans, calc(arr[ 0 ], arr[ 1 ])) # Update ans by choosing the pair # of maximum and 2nd maximum ans = max (ans, calc(arr[N - 2 ],arr[N - 1 ])) # Return the value of ans return ans # Driver Code if __name__ = = '__main__' : arr = [ 0 , - 47 , 12 ] N = len (arr) print (findMaximum(arr, N)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the value of // the expression a * b + (b - a) static int calc( int a, int b) { return a * b + (b - a); } // Function to find the maximum value // of the expression a * b + (b - a) // possible for any pair (a, b) static int findMaximum(List< int > arr, int N) { // Sort the vector in ascending order arr.Sort(); // Stores the maximum value int ans = -1000000000; // Update ans by choosing the pair // of the minimum and 2nd minimum ans = Math.Max(ans, calc(arr[0], arr[1])); // Update ans by choosing the pair // of maximum and 2nd maximum ans = Math.Max(ans, calc(arr[N - 2], arr[N - 1])); // Return the value of ans return ans; } // Driver Code public static void Main() { List< int > arr = new List< int >{ 0, -47, 12 }; int N = ( int )arr.Count; Console.Write(findMaximum(arr, N)); } } // This code is contributed by ukasp.. |
Javascript
<script> // Javascript program for the above approach // Function to find the value of // the expression a * b + (b - a) function calc(a, b) { return (a * b) + (b - a); } // Function to find the maximum value // of the expression a * b + (b - a) // possible for any pair (a, b) function findMaximum(arr, N) { // Sohe vector in ascending order arr.sort( function (a, b){ return a - b}) // Stores the maximum value let ans = Number.MIN_VALUE; // Update ans by choosing the pair // of the minimum and 2nd minimum ans = Math.max(ans, calc(arr[0], arr[1])); // Update ans by choosing the pair // of maximum and 2nd maximum ans = Math.max(ans, calc(arr[N - 2], arr[N - 1])); // Return the value of ans return ans; } // Driver Code // Given inputs let arr = [-47, 0, 12] let N = arr.length; document.write(findMaximum(arr, N)); // This code is contributed by Hritik </script> |
47
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us