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 differenceclass 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 orderbool 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 arraysint 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 Codeint 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 differenceclass 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 differenceclass 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 differenceclass 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 arraysfunction 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 Codelet A = [1, 4, 1, 2]let B = [4, 3, 2, 5]let n = A.lengthlet X = 2, Y = 2document.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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
