Maximize the sum of X+Y elements by picking X and Y elements from 1st and 2nd array
Given two arrays of size N, and two numbers X and Y, the task is to maximize the sum by considering the below points:
- Pick x values from the first array and y values from the second array such that the sum of X+Y values is maximum.
- It is given that X + Y is equal to N.
Examples:
Input: arr1[] = {1, 4, 1}, arr2[] = {2, 5, 3}, N = 3, X = 2, Y = 1
Output: 8
In order to maximize sum from 2 arrays,
pick 1st and 2nd element from first array and 3rd from second array.Input: A[] = {1, 4, 1, 2}, B[] = {4, 3, 2, 5}, N = 4, X = 2, Y = 2
Output: 14
Approach: A greedy approach can be used to solve the above problem. Below are the required steps:
- Find those elements of arrays first that have maximum value by finding the highest difference between elements of two arrays.
- For that, find the absolute difference between the value of the first and second array and then store it in some another array.
- Sort this array in decreasing order.
- While sorting, track the original positions of elements in the arrays.
- Now compare the elements of the two arrays and add the greater value to the maxAmount.
- If both have the same value, add an element of the first array if X is not zero else add an element of the second array.
- After traversing the arrays completely return the maxAmount calculated.
Below is the implementation of above approach :
C++
// C++ program to print the maximum // possible sum from two arrays. #include <bits/stdc++.h> using namespace std; // class that store values of two arrays // and also store their absolute difference class triplet { public : int first; int second; int diff; triplet( int f, int s, int d) : first(f), second(s), diff(d) { } }; // Compare function used to sort array in decreasing order bool compare(triplet& a, triplet& b) { return a.diff > b.diff; // decreasing order } /// Function to find the maximum possible /// sum that can be generated from 2 arrays int findMaxAmount( int arr1[], int arr2[], int n, int x, int y) { // vector where each index stores 3 things: // Value of 1st array // Value of 2nd array // Their absolute difference vector<triplet> v; for ( int i = 0; i < n; i++) { triplet t(arr1[i], arr2[i], abs (arr1[i] - arr2[i])); v.push_back(t); } // sort according to their absolute difference sort(v.begin(), v.end(), compare); // it will store maximum sum int maxAmount = 0; int i = 0; // Run loop for N times or // value of X or Y becomes zero while (i < n && x > 0 && y > 0) { // if 1st array element has greater // value, add it to maxAmount if (v[i].first > v[i].second) { maxAmount += v[i].first; x--; } // if 2nd array element has greater // value, add it to maxAmount if (v[i].first < v[i].second) { maxAmount += v[i].second; y--; } // if both have same value, add element // of first array if X is not zero // else add element of second array if (v[i].first == v[i].second) { if (x > 0) { maxAmount += v[i].first; x--; } else if (y > 0) { maxAmount += v[i].second; y--; } } // increment after picking element i++; } // add the remaining values // of first array to maxAmount while (i < v.size() && x--) { maxAmount += v[i++].first; } // add the remaining values of // second array to maxAmount while (i < v.size() && y--) { maxAmount += v[i++].second; } return maxAmount; } // Driver Code int main() { int A[] = { 1, 4, 1, 2 }; int B[] = { 4, 3, 2, 5 }; int n = sizeof (A) / sizeof (A[0]); int X = 2, Y = 2; cout << findMaxAmount(A, B, n, X, Y) << "\n" ; } |
Java
// Java program to print the maximum // possible sum from two arrays. import java.util.*; // class that store values of two arrays // and also store their absolute difference class Triplet implements Comparable<Triplet> { int first; int second; int diff; Triplet( int f, int s, int d) { first = f; second = s; diff = d; } // CompareTo function used to sort // array in decreasing order public int compareTo(Triplet o) { return o.diff - this .diff; } } class GFG{ // Function to find the maximum possible // sum that can be generated from 2 arrays public static int findMaxAmount( int arr1[], int arr2[], int n, int x, int y) { // Vector where each index // stores 3 things: // Value of 1st array // Value of 2nd array // Their absolute difference Vector<Triplet> v = new Vector<>(); for ( int i = 0 ; i < n; i++) { v.add( new Triplet(arr1[i], arr2[i], Math.abs(arr1[i] - arr2[i]))); } // Sort according to their // absolute difference Collections.sort(v); // It will store maximum sum int maxAmount = 0 ; int i = 0 ; // Run loop for N times or // value of X or Y becomes zero while (i < n && x > 0 && y > 0 ) { // If 1st array element has greater // value, add it to maxAmount if (v.get(i).first > v.get(i).second) { maxAmount += v.get(i).first; x--; } // If 2nd array element has greater // value, add it to maxAmount if (v.get(i).first < v.get(i).second) { maxAmount += v.get(i).second; y--; } // If both have same value, add element // of first array if X is not zero // else add element of second array if (v.get(i).first == v.get(i).second) { if (x > 0 ) { maxAmount += v.get(i).first; x--; } else if (y > 0 ) { maxAmount += v.get(i).second; y--; } } // Increment after picking element i++; } // Add the remaining values // of first array to maxAmount while (i < v.size() && x-- > 0 ) { maxAmount += v.get(i++).first; } // Add the remaining values of // second array to maxAmount while (i < v.size() && y-- > 0 ) { maxAmount += v.get(i++).second; } return maxAmount; } // Driver Code public static void main(String []args) { int A[] = { 1 , 4 , 1 , 2 }; int B[] = { 4 , 3 , 2 , 5 }; int n = A.length; int X = 2 , Y = 2 ; System.out.println(findMaxAmount(A, B, n, X, Y)); } } // This code is contributed by jrishabh99 |
Python3
# Python3 program to print the maximum # possible sum from two arrays. # Class that store values of two arrays # and also store their absolute difference class triplet: def __init__( self , f, s, d): self .first = f self .second = s self .diff = d # Function to find the maximum possible # sum that can be generated from 2 arrays def findMaxAmount(arr1, arr2, n, x, y): # vector where each index stores 3 things: # Value of 1st array # Value of 2nd array # Their absolute difference v = [] for i in range ( 0 , n): t = triplet(arr1[i], arr2[i], abs (arr1[i] - arr2[i])) v.append(t) # sort according to their absolute difference v.sort(key = lambda x: x.diff, reverse = True ) # it will store maximum sum maxAmount, i = 0 , 0 # Run loop for N times or # value of X or Y becomes zero while i < n and x > 0 and y > 0 : # if 1st array element has greater # value, add it to maxAmount if v[i].first > v[i].second: maxAmount + = v[i].first x - = 1 # if 2nd array element has greater # value, add it to maxAmount if v[i].first < v[i].second: maxAmount + = v[i].second y - = 1 # if both have same value, add element # of first array if X is not zero # else add element of second array if v[i].first = = v[i].second: if x > 0 : maxAmount + = v[i].first x - = 1 elif y > 0 : maxAmount + = v[i].second y - = 1 # increment after picking element i + = 1 # add the remaining values # of first array to maxAmount while i < len (v) and x > 0 : maxAmount + = v[i].first i, x = i + 1 , x - 1 # add the remaining values of # second array to maxAmount while i < len (v) and y > 0 : maxAmount + = v[i].second i, y = i + 1 , y - 1 return maxAmount # Driver Code if __name__ = = "__main__" : A = [ 1 , 4 , 1 , 2 ] B = [ 4 , 3 , 2 , 5 ] n = len (A) X, Y = 2 , 2 print (findMaxAmount(A, B, n, X, Y)) # This code is contributed by Rituraj Jain |
C#
// C# program to print the maximum // possible sum from two arrays. using System; using System.Collections.Generic; // class that store values of two arrays // and also store their absolute difference class Triplet : IComparable<Triplet> { public int first; public int second; public int diff; public Triplet( int f, int s, int d) { first = f; second = s; diff = d; } // CompareTo function used to sort // array in decreasing order public int CompareTo(Triplet o) { return o.diff - this .diff; } } class GFG { // Function to find the maximum possible // sum that can be generated from 2 arrays public static int findMaxAmount( int [] arr1, int [] arr2, int n, int x, int y) { // List where each index // stores 3 things: // Value of 1st array // Value of 2nd array // Their absolute difference List<Triplet> v = new List<Triplet>(); for ( int j = 0; j < n; j++) { v.Add( new Triplet(arr1[j], arr2[j], Math.Abs(arr1[j] - arr2[j]))); } // Sort according to their // absolute difference v.Sort(); // It will store maximum sum int maxAmount = 0; int i = 0; // Run loop for N times or // value of X or Y becomes zero while (i < n && x > 0 && y > 0) { // If 1st array element has greater // value, add it to maxAmount if (v[i].first > v[i].second) { maxAmount += v[i].first; x--; } // If 2nd array element has greater // value, add it to maxAmount if (v[i].first < v[i].second) { maxAmount += v[i].second; y--; } // If both have same value, add element // of first array if X is not zero // else add element of second array if (v[i].first == v[i].second) { if (x > 0) { maxAmount += v[i].first; x--; } else if (y > 0) { maxAmount += v[i].second; y--; } } // Increment after picking element i++; } // Add the remaining values // of first array to maxAmount while (i < v.Count && x-- > 0) { maxAmount += v[i++].first; } // Add the remaining values of // second array to maxAmount while (i < v.Count && y-- > 0) { maxAmount += v[i++].second; } return maxAmount; } // Driver Code public static void Main( string [] args) { int [] A = { 1, 4, 1, 2 }; int [] B = { 4, 3, 2, 5 }; int n = A.Length; int X = 2, Y = 2; Console.WriteLine(findMaxAmount(A, B, n, X, Y)); } } |
Javascript
<script> // JavaScript program to print the maximum // possible sum from two arrays. // Class that store values of two arrays // && also store their absolute difference class triplet{ constructor(f, s, d){ this .first = f this .second = s this .diff = d } } // Function to find the maximum possible // sum that can be generated from 2 arrays function findMaxAmount(arr1, arr2, n, x, y){ // vector where each index stores 3 things: // Value of 1st array // Value of 2nd array // Their absolute difference let v = [] for (let i = 0; i < n; i++){ let t = new triplet(arr1[i], arr2[i], Math.abs(arr1[i] - arr2[i])) v.push(t) } // sort according to their absolute difference v.sort((a,b) => b.diff - a.diff) // it will store maximum sum let maxAmount=0, i = 0 // Run loop for N times or // value of X or Y becomes zero while (i < n && x > 0 && y > 0){ // if 1st array element has greater // value, add it to maxAmount if (v[i].first > v[i].second){ maxAmount += v[i].first x -= 1 } // if 2nd array element has greater // value, add it to maxAmount if (v[i].first < v[i].second){ maxAmount += v[i].second y -= 1 } // if both have same value, add element // of first array if X is not zero // else add element of second array if (v[i].first == v[i].second){ if (x > 0){ maxAmount += v[i].first x-- } else if (y > 0){ maxAmount += v[i].second y-- } } // increment after picking element i++ } // add the remaining values // of first array to maxAmount while (i < v.length && x > 0){ maxAmount += v[i].first i++ x-- } // add the remaining values of // second array to maxAmount while (i < v.length && y > 0){ maxAmount += v[i].second i++ y-- } return maxAmount } // Driver Code let A = [1, 4, 1, 2] let B = [4, 3, 2, 5] let n = A.length let X = 2, Y = 2 document.write(findMaxAmount(A, B, n, X, Y)) // This code is contributed by shinjanpatra </script> |
Output
14
complexity Analysis:
- Time complexity: O(N log N)
- Auxiliary Space: O(N)