Given an array arr[] of N integers where N is even, the task is to group the array elements in the pairs (X1, Y1), (X2, Y2), (X3, Y3), … such that the sum min(X1, Y1) + min(X2, Y2) + min(X3, Y3) + … is maximum.
Examples:
Input: arr[] = {1, 5, 3, 2}
Output: 4
(1, 5) and (3, 2) -> 1 + 2 = 3
(1, 3) and (5, 2) -> 1 + 2 = 3
(1, 2) and (5, 3) -> 1 + 3 = 4
Input: arr[] = {1, 3, 2, 1, 4, 5}
Output: 7
Approach: No matter how the pairs are formed, the maximum element from the array will always be ignored as it will be the maximum element in every pair it is put into. Same goes for the second maximum element unless it is paired with the maximum element. So, to maximize the sum an optimal approach will be to sort the array and start making pairs in order starting from the maximum element.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum// required sum of the pairsint maxSum(int a[], int n){ // Sort the array sort(a, a + n); // To store the sum int sum = 0; // Start making pairs of every two // consecutive elements as n is even for (int i = 0; i < n - 1; i += 2) { // Minimum element of the current pair sum += a[i]; } // Return the maximum possible sum return sum;}// Driver codeint main(){ int arr[] = { 1, 3, 2, 1, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); cout << maxSum(arr, n); return 0;} |
Java
// Java implementation of the approachimport java.util.Arrays;class GFG{ // Function to return the maximum// required sum of the pairsstatic int maxSum(int a[], int n){ // Sort the array Arrays.sort(a); // To store the sum int sum = 0; // Start making pairs of every two // consecutive elements as n is even for (int i = 0; i < n - 1; i += 2) { // Minimum element of the current pair sum += a[i]; } // Return the maximum possible sum return sum;}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 3, 2, 1, 4, 5 }; int n = arr.length; System.out.println(maxSum(arr, n));}}// This code is contributed by Code_Mech |
Python3
# Python3 implementation of the approach # Function to return the maximum # required sum of the pairs def maxSum(a, n) : # Sort the array a.sort(); # To store the sum sum = 0; # Start making pairs of every two # consecutive elements as n is even for i in range(0, n - 1, 2) : # Minimum element of the current pair sum += a[i]; # Return the maximum possible sum return sum; # Driver code if __name__ == "__main__" : arr = [ 1, 3, 2, 1, 4, 5 ]; n = len(arr); print(maxSum(arr, n));# This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG{ // Function to return the maximum// required sum of the pairsstatic int maxSum(int []a, int n){ // Sort the array Array.Sort(a); // To store the sum int sum = 0; // Start making pairs of every two // consecutive elements as n is even for (int i = 0; i < n - 1; i += 2) { // Minimum element of the current pair sum += a[i]; } // Return the maximum possible sum return sum;}// Driver codepublic static void Main(String[] args){ int []arr = { 1, 3, 2, 1, 4, 5 }; int n = arr.Length; Console.WriteLine(maxSum(arr, n));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function to return the maximum// required sum of the pairsfunction maxSum(a, n) { // Sort the array a.sort((a, b) => a - b); // To store the sum let sum = 0; // Start making pairs of every two // consecutive elements as n is even for (let i = 0; i < n - 1; i += 2) { // Minimum element of the current pair sum += a[i]; } // Return the maximum possible sum return sum;}// Driver codelet arr = [1, 3, 2, 1, 4, 5];let n = arr.length;document.write(maxSum(arr, n));// This code is contributed by _saurabh_jaiswal</script> |
7
Time Complexity: O(n logn)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
