Maximum sum by picking elements from two arrays in order
Given two arrays of size N and two integers X and Y indicating the maximum number of elements, one can pick from array A and array B respectively.
At each ith turn, either A[i] or B[i] can be picked. The task is to make the selection that results in the maximum possible sum.
Note: It is guaranteed that (X + Y) ≥ N.
Examples:
Input: A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1}, X = 3, Y = 2
Output: 21
i = 0 -> 5 picked
i = 1 -> 4 picked
i = 2 -> 3 picked
i = 3 -> 4 picked
i = 4 -> 5 picked
5 + 4 + 3 + 4 + 5 = 21
Input: A[] = {1, 4, 3, 2, 7, 5, 9, 6}, B[] = {1, 2, 3, 6, 5, 4, 9, 8}, X = 4, Y = 4
Output: 43
Approach: Use the greedy approach to select the elements that will result in the maximum sum. The following steps will help in solving this problem:
- Sort the element pairs according to the absolute difference i.e. |A[i] – B[i]| in decreasing order.
- Compare A[i] and B[i] value, the one which is greater adds that value to the sum.
- Decrement X by one if the element is chosen from A[i] else decrement Y by one.
- Print the sum in the end.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; long long getMaximumSum(vector< int > a, vector< int >b, int n, int x, int y) { vector<vector< int > > v; long long tsum=0; for ( int i=0;i<n;i++) { v.push_back({ abs (a[i]-b[i]),a[i],b[i]}); } sort(v.begin(),v.end(),greater<vector< int > >()); for ( int i=0;i<v.size();i++) { if (v[i][1]>v[i][2] && x>0) { tsum+=v[i][1]; x--; } else if (v[i][1]<v[i][2] && y>0) { tsum+=v[i][2]; y--; } else { tsum+=min(v[i][2],v[i][1]); } } return tsum; } int main() { int x = 3, y = 2; vector< int > a= { 1, 2, 3, 4, 5 }; vector< int > b= { 5, 4, 3, 2, 1 }; int n = a.size(); cout<<getMaximumSum(a, b, n, x, y); return 0; } |
Java
// Java program to calculate the // maximum sum obtained by making an // Optimal selection of elements from two given arrays import java.io.*; import java.util.*; import java.lang.*; // User defined Pair class class Pair { int x; int y; // Constructor public Pair( int x, int y) { this .x = x; this .y = y; } } // Class to define user defined comparator class Compare { // Function to reverse the elements of an array static void reverseArray(Pair[] arr, int start, int end) { int tempx, tempy; while (start < end) { tempx = arr[start].x; tempy = arr[start].y; arr[start].x = arr[end].x; arr[start].y = arr[end].y; arr[end].x = tempx; arr[end].y = tempy; start++; end--; } } // Function to sort the pair according to the // absolute differences static Pair[] compare(Pair[] arr, int N) { // Comparator to sort the pair according to // the absolute differences Arrays.sort(arr, new Comparator<Pair>() { @Override public int compare(Pair p1, Pair p2) { return (Math.abs(p1.x - p1.y) - Math.abs(p2.x - p2.y)); } }); // To get in descending order reverseArray(arr, 0 , N - 1 ); return arr; } } // Driver class class GFG { // Function to calculate the // maximum possible sum obtained by making an // optimal selection elements from two given arrays static int getMaximumSum( int [] A, int [] B, int N, int X, int Y) { int num1, num2, sum = 0 ; // Making a single pair array having // arr[i] element as (Ai, Bi) Pair[] arr = new Pair[N]; for ( int i = 0 ; i < N; i++) { arr[i] = new Pair(A[i], B[i]); } // Sorting according to the absolute differences // in the decreasing order Compare obj = new Compare(); obj.compare(arr, N); // Applying Greedy approach to make an optimal // selection for ( int i = 0 ; i < N; i++) { num1 = arr[i].x; num2 = arr[i].y; // If A[i] > B[i] if (num1 > num2) { // If element from A can be picked if (X > 0 ) { sum += num1; X--; } // Insufficient X // Make a pick from B else if (Y > 0 ) { sum += num2; Y--; } } // If B[i] > A[i] else if (num2 > num1 && Y > 0 ) { // If element from B can be picked if (Y > 0 ) { sum += num2; Y--; } // Insufficient Y // Make a pick from A else { sum += num1; X--; } } // If A[i] = B[i] // Doesn't make a difference so any value // can be picked else { sum += num1; if (X > 0 ) { X--; } else if (Y > 0 ) Y--; } } return sum; } // Driver code public static void main(String args[]) { int X = 3 , Y = 2 ; int [] A = { 1 , 2 , 3 , 4 , 5 }; int [] B = { 5 , 4 , 3 , 2 , 1 }; int N = A.length; System.out.println(getMaximumSum(A, B, N, X, Y)); } } |
Python3
from typing import List def get_maximum_sum(a: List [ int ], b: List [ int ], n: int , x: int , y: int ) - > int : v = [] tsum = 0 for i in range (n): v.append([ abs (a[i] - b[i]), a[i], b[i]]) v.sort(key = lambda x: x[ 0 ], reverse = True ) for i in range ( len (v)): if v[i][ 1 ] > v[i][ 2 ] and x > 0 : tsum + = v[i][ 1 ] x - = 1 elif v[i][ 1 ] < v[i][ 2 ] and y > 0 : tsum + = v[i][ 2 ] y - = 1 else : tsum + = min (v[i][ 2 ], v[i][ 1 ]) return tsum x = 3 y = 2 a = [ 1 , 2 , 3 , 4 , 5 ] b = [ 5 , 4 , 3 , 2 , 1 ] n = len (a) print (get_maximum_sum(a, b, n, x, y)) |
C#
using System; using System.Linq; using System.Collections.Generic; class GFG { static long getMaximumSum(List< int > a, List< int > b, int n, int x, int y) { List<List< int >> v = new List<List< int >>(); long tsum=0; for ( int i=0;i<n;i++) { v.Add( new List< int >(){Math.Abs(a[i]-b[i]),a[i],b[i]}); } v = v.OrderByDescending(arr => arr[0]).ToList(); for ( int i=0;i<v.Count;i++) { if (v[i][1]>v[i][2] && x>0) { tsum+=v[i][1]; x--; } else if (v[i][1]<v[i][2] && y>0) { tsum+=v[i][2]; y--; } else { tsum+=Math.Min(v[i][2],v[i][1]); } } return tsum; } public static void Main ( string [] args) { int x = 3, y = 2; List< int > a= new List< int > { 1, 2, 3, 4, 5 }; List< int > b= new List< int > { 5, 4, 3, 2, 1 }; int n = a.Count; Console.WriteLine(getMaximumSum(a, b, n, x, y)); } } |
Javascript
<script> // Javascript program for the above approach function getMaximumSum( a, b, n, x, y) { let v=[]; let tsum=0; for (let i=0;i<n;i++) { v.push([(Math.abs(a[i]-b[i]),a[i],b[i])]); } v.sort(); v.reverse(); for (let i=0;i<v.length;i++) { if (v[i][1]>v[i][2] && x>0) { tsum+=v[i][1]; x--; } else if (v[i][1]<v[i][2] && y>0) { tsum+=v[i][2]; y--; } else { tsum+=Math.min(v[i][2],v[i][1]); } } return tsum; } // Driver Code let x = 3; let y = 2; let a= [ 1, 2, 3, 4, 5 ]; let b= [ 5, 4, 3, 2, 1 ]; let n = a.length; document.write(getMaximumSum(a, b, n, x, y)); // This program is contributed by Pushpesh Raj. </script> |
21
Time Complexity: O(n*log(n))
Auxiliary Space: O(n)
METHOD 2:Using heapq method
APPROACH:
This approach uses a heap data structure to keep track of the maximum elements from both arrays.
ALGORITHM:
1.Create two heaps of tuples with the sum of each element from array A and B, and the index of the element.
2.Initialize a sum variable to 0.
3.Iterate X times and pick the maximum element from either heap and add it to the sum variable.
4.Iterate Y times and pick the maximum element from either heap and add it to the sum variable.
5.Return the sum variable as the maximum sum.
C++
#include <iostream> #include <vector> #include <queue> using namespace std; struct Compare { bool operator()(pair< int , int >& a, pair< int , int >& b) { return a.first > b.first; // Min-heap based on the first element } }; int max_sum_4(vector< int >& A, vector< int >& B, int X, int Y) { priority_queue<pair< int , int >, vector<pair< int , int >>, Compare> hA, hB; for ( int i = 0; i < A.size(); i++) hA.push(make_pair(-A[i], i)); for ( int j = 0; j < B.size(); j++) hB.push(make_pair(-B[j], j)); int sum = 0; for ( int i = 0; i < X; i++) { if (!hB.empty() && (-hA.top().first >= -hB.top().first)) { sum += -hA.top().first; hA.pop(); } else { sum += -hB.top().first; hB.pop(); } } for ( int j = 0; j < Y; j++) { if (!hA.empty() && (-hB.top().first >= -hA.top().first)) { sum += -hB.top().first; hB.pop(); } else { sum += -hA.top().first; hA.pop(); } } return sum; } int main() { vector< int > A = {1, 2, 3, 4, 5}; vector< int > B = {5, 4, 3, 2, 1}; int X = 3; int Y = 2; cout << max_sum_4(A, B, X, Y) << endl; // Output: 21 return 0; } |
Java
import java.util.*; class Main { // Custom Comparator for min-heap based on the first element of the pair static class Compare implements Comparator<Pair<Integer, Integer>> { public int compare(Pair<Integer, Integer> a, Pair<Integer, Integer> b) { return Integer.compare(a.getKey(), b.getKey()); } } public static int max_sum_4(List<Integer> A, List<Integer> B, int X, int Y) { PriorityQueue<Pair<Integer, Integer>> hA = new PriorityQueue<>( new Compare()); PriorityQueue<Pair<Integer, Integer>> hB = new PriorityQueue<>( new Compare()); for ( int i = 0 ; i < A.size(); i++) hA.add( new Pair<>(-A.get(i), i)); for ( int j = 0 ; j < B.size(); j++) hB.add( new Pair<>(-B.get(j), j)); int sum = 0 ; for ( int i = 0 ; i < X; i++) { if (!hB.isEmpty() && -hA.peek().getKey() >= -hB.peek().getKey()) { sum += -hA.peek().getKey(); hA.poll(); } else { sum += -hB.peek().getKey(); hB.poll(); } } for ( int j = 0 ; j < Y; j++) { if (!hA.isEmpty() && -hB.peek().getKey() >= -hA.peek().getKey()) { sum += -hB.peek().getKey(); hB.poll(); } else { sum += -hA.peek().getKey(); hA.poll(); } } return sum; } public static void main(String[] args) { List<Integer> A = Arrays.asList( 1 , 2 , 3 , 4 , 5 ); List<Integer> B = Arrays.asList( 5 , 4 , 3 , 2 , 1 ); int X = 3 ; int Y = 2 ; System.out.println(max_sum_4(A, B, X, Y)); // Output: 21 } } // Simple Pair class implementation class Pair<K, V> { private final K key; private final V value; public Pair(K key, V value) { this .key = key; this .value = value; } public K getKey() { return key; } public V getValue() { return value; } } |
Python3
import heapq def max_sum_4(A, B, X, Y): hA = [( - A[i], i) for i in range ( len (A))] hB = [( - B[j], j) for j in range ( len (B))] heapq.heapify(hA) heapq.heapify(hB) sum = 0 for i in range (X): if hA and ( not hB or - hA[ 0 ][ 0 ] > = - hB[ 0 ][ 0 ]): sum + = - hA[ 0 ][ 0 ] heapq.heappop(hA) else : sum + = - hB[ 0 ][ 0 ] heapq.heappop(hB) for j in range (Y): if hB and ( not hA or - hB[ 0 ][ 0 ] > = - hA[ 0 ][ 0 ]): sum + = - hB[ 0 ][ 0 ] heapq.heappop(hB) else : sum + = - hA[ 0 ][ 0 ] heapq.heappop(hA) return sum A = [ 1 , 2 , 3 , 4 , 5 ] B = [ 5 , 4 , 3 , 2 , 1 ] X = 3 Y = 2 print (max_sum_4(A, B, X, Y)) # Output: 21 |
C#
using System; using System.Collections.Generic; class Program { public class PairComparer : IComparer<Tuple< int , int >> { public int Compare(Tuple< int , int > a, Tuple< int , int > b) { return a.Item1.CompareTo(b.Item1); } } public static int MaxSum4(List< int > A, List< int > B, int X, int Y) { PriorityQueue<Tuple< int , int >> hA = new PriorityQueue<Tuple< int , int >>( new PairComparer()); PriorityQueue<Tuple< int , int >> hB = new PriorityQueue<Tuple< int , int >>( new PairComparer()); for ( int i = 0; i < A.Count; i++) hA.Enqueue( new Tuple< int , int >(-A[i], i)); for ( int j = 0; j < B.Count; j++) hB.Enqueue( new Tuple< int , int >(-B[j], j)); int sum = 0; for ( int i = 0; i < X; i++) { if (hB.Count > 0 && (-hA.Peek().Item1 >= -hB.Peek().Item1)) { sum += -hA.Peek().Item1; hA.Dequeue(); } else { sum += -hB.Peek().Item1; hB.Dequeue(); } } for ( int j = 0; j < Y; j++) { if (hA.Count > 0 && (-hB.Peek().Item1 >= -hA.Peek().Item1)) { sum += -hB.Peek().Item1; hB.Dequeue(); } else { sum += -hA.Peek().Item1; hA.Dequeue(); } } return sum; } static void Main( string [] args) { List< int > A = new List< int > { 1, 2, 3, 4, 5 }; List< int > B = new List< int > { 5, 4, 3, 2, 1 }; int X = 3; int Y = 2; Console.WriteLine(MaxSum4(A, B, X, Y)); // Output: 21 } } public class PriorityQueue<T> { private List<T> data; private IComparer<T> comparer; public int Count => data.Count; public PriorityQueue(IComparer<T> comparer) { this .data = new List<T>(); this .comparer = comparer; } public void Enqueue(T item) { data.Add(item); int ci = data.Count - 1; // child index; start at end while (ci > 0) { int pi = (ci - 1) / 2; // parent index if (comparer.Compare(data[ci], data[pi]) >= 0) break ; // child item is larger than (or equal) parent, so we're done T tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp; ci = pi; } } public T Dequeue() { int li = data.Count - 1; // last index (before removal) T frontItem = data[0]; // fetch the front data[0] = data[li]; data.RemoveAt(li); --li; // last index (after removal) int pi = 0; // parent index. start at front of pq while ( true ) { int ci = pi * 2 + 1; // left child index of parent if (ci > li) break ; // no children so done int rc = ci + 1; // right child if (rc <= li && comparer.Compare(data[rc], data[ci]) < 0) ci = rc; // if there is a rc (ci + 1), and it is smaller than left child, use the rc instead if (comparer.Compare(data[pi], data[ci]) <= 0) break ; // parent is smaller than (or equal to) smallest child so done T tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp; // swap parent and child pi = ci; } return frontItem; } public T Peek() { T frontItem = data[0]; return frontItem; } } |
Javascript
class PriorityQueue { constructor(compareFunction) { this .queue = []; this .compare = compareFunction; } // Add an element to the priority queue and maintain the order using the compare function. add(element) { this .queue.push(element); this .queue.sort( this .compare); } // Remove and return the highest priority element from the queue. poll() { if (! this .isEmpty()) { return this .queue.shift(); } return null ; } // Return the highest priority element without removing it from the queue. peek() { return this .isEmpty() ? null : this .queue[0]; } // Check if the priority queue is empty. isEmpty() { return this .queue.length === 0; } } class Pair { constructor(key, value) { this .key = key; this .value = value; } getKey() { return this .key; } getValue() { return this .value; } } function max_sum_4(A, B, X, Y) { // Create two priority queues, hA and hB, with custom compare functions. const hA = new PriorityQueue((a, b) => a.getKey() - b.getKey()); const hB = new PriorityQueue((a, b) => a.getKey() - b.getKey()); // Populate priority queue hA with pairs (value, index) from array A, sorted by value in ascending order. for (let i = 0; i < A.length; i++) { hA.add( new Pair(-A[i], i)); // Using negative values for sorting in descending order. } // Populate priority queue hB with pairs (value, index) from array B, sorted by value in ascending order. for (let j = 0; j < B.length; j++) { hB.add( new Pair(-B[j], j)); // Using negative values for sorting in descending order. } let sum = 0; // Pick the top X elements from the priority queues hA and hB alternatively and add their values to the sum. for (let i = 0; i < X; i++) { if (!hB.isEmpty() && -hA.peek().getKey() >= -hB.peek().getKey()) { sum += -hA.peek().getKey(); // Add the value from hA to the sum. hA.poll(); // Remove the element from hA. } else { sum += -hB.peek().getKey(); // Add the value from hB to the sum. hB.poll(); // Remove the element from hB. } } // Pick the top Y elements from the priority queues hA and hB alternatively and add their values to the sum. for (let j = 0; j < Y; j++) { if (!hA.isEmpty() && -hB.peek().getKey() >= -hA.peek().getKey()) { sum += -hB.peek().getKey(); // Add the value from hB to the sum. hB.poll(); // Remove the element from hB. } else { sum += -hA.peek().getKey(); // Add the value from hA to the sum. hA.poll(); // Remove the element from hA. } } return sum; // Return the final sum. } const A = [1, 2, 3, 4, 5]; const B = [5, 4, 3, 2, 1]; const X = 3; const Y = 2; console.log(max_sum_4(A, B, X, Y)); // Output: 21 |
21
This algorithm has a time complexity of O((X+Y)log(N)) where N is the maximum length of both arrays A and B. This is because we perform X+Y iterations of picking the maximum element from a heap which takes O(log(N)) time. The space complexity of this algorithm is O(N) because we store both arrays A and B in the heap data structures.