Given an array A[] of length N, choose any two elements x and y from the array, the task is to find the maximum value of the expression (x * y + x – y).
Examples:
Input: A[] = {5, 2, 3}
Output: 17
Explanation: There are six possible pairs:
For pairs {2, 3} and {3, 2}, answer = 2 ? 3 + max(2?3, 3?2) = 7
For pairs {3, 5} and {5, 3} answer = 5 ? 3 + max(3?5, 5?3) = 17 and
For pairs {2, 5} and {5, 2}, answer = 2 ? 5 + max(2?5, 5?2) = 13.
So final answer is maximum of {7, 17, 13} = 17.Input: A[] = {3, 7, 4, 9}
Output: 65
Approach: The problem can be solved based on the following observation:
Rewriting x?y + x?y = (x?1)?(y+1) + 1
To maximize the value of the expression we have to maximize the value of x*y.
So there can be two choices:
- If the minimum and second minimum both are negative, their product will be positive and that can be a valid answer.
- If the maximum and second maximum both are positive, their product will be positive and that can be the required pair.
So find the minimum and second minimum and maximum and second maximum and check for the above cases. The maximum will be the answer.
Follow the below steps to implement the above idea:
- First sort the array.
- Select minimum, second minimum, maximum, and second maximum element of the array.
- After that find the value of expression for x = minimum and y = second minimum & x = maximum and y = second maximum and store them in sum1 and sum2 respectively.
- Find the maximum between sum1 and sum2 and print that value
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>#include <iostream>using namespace std;int maxValue(int array[], int n){ sort(array, array + n); int a1 = array[0]; int b1 = array[1]; int b2 = array[n - 2]; int a2 = array[n - 1]; int sum1; int sum2; sum1 = a1 * b1 + max(a1 - b1, b1 - a1); sum2 = a2 * b2 + max(b2 - a2, a2 - b2); return max(sum1, sum2);}int main(){ int arr[] = { 5, 2, 3 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << maxValue(arr, N) << endl; return 0;}// This code is contributed by lokeshmvs21. |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to find maximum value of expression public static int maxValue(int array[], int n) { Arrays.sort(array); int a1 = array[0]; int b1 = array[1]; int b2 = array[n - 2]; int a2 = array[n - 1]; int sum1; int sum2; sum1 = a1 * b1 + Math.max(a1 - b1, b1 - a1); sum2 = a2 * b2 + Math.max(b2 - a2, a2 - b2); return Math.max(sum1, sum2); } // Driver Code public static void main(String[] args) { int arr[] = { 5, 2, 3 }; int N = arr.length; // Function call System.out.println(maxValue(arr, N)); }} |
Python3
# Python code to implement the approach# Function to find maximum value of expressiondef maxValue(array, n): array.sort() a1 = array[0] b1 = array[1] b2 = array[n - 2] a2 = array[n - 1] sum1 = a1 * b1 + max(a1 - b1, b1 - a1) sum2 = a2 * b2 + max(b2 - a2, a2 - b2) return max(sum1, sum2) # Driver Codeif __name__ == '__main__': arr = [5, 2, 3] N = len(arr) # Function call print(maxValue(arr, N)) |
C#
// C# code to implement the approachusing System;class GFG { // Function to find maximum value of expression public static int maxValue(int[] array, int n) { Array.Sort(array); int a1 = array[0]; int b1 = array[1]; int b2 = array[n - 2]; int a2 = array[n - 1]; int sum1; int sum2; sum1 = a1 * b1 + Math.Max(a1 - b1, b1 - a1); sum2 = a2 * b2 + Math.Max(b2 - a2, a2 - b2); return Math.Max(sum1, sum2); }// Driver Codepublic static void Main(){ int[] arr = { 5, 2, 3 }; int N = arr.Length; // Function call Console.Write(maxValue(arr, N));}}// This code is contributed by code_hunt. |
Javascript
// Javascript code to implement the approach<script>// Function to find maximum value of expressionfunction maxValue(array, n){ array.sort(); let a1 = array[0]; let b1 = array[1]; let b2 = array[n - 2]; let a2 = array[n - 1]; let sum1; let sum2; sum1 = a1 * b1 + Math.max(a1 - b1, b1 - a1); sum2 = a2 * b2 + Math.max(b2 - a2, a2 - b2); return Math.max(sum1, sum2); } // Driver code let arr = [ 5, 2, 3 ]; let N = arr.length; // Function call console.log(maxValue(arr, N)); </script> |
17
Time Complexity: O(N*log(N)) //the inbuilt sort function takes N log N time to complete all operations, hence the overall time taken by the algorithm is N log N
Auxiliary Space: O(1) // since no extra array is used so the space taken by the algorithm is constant
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
