Given two arrays A[] and B[], each of size N, and two integers X and Y denoting the maximum number of elements that can be picked from A[] and B[] respectively, the task is to find the maximum possible sum by selecting N elements in such a way that for any index i, either A[i] or B[i] can be chosen.
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
Greedy Approach: The greedy approach to solve this problem has already been discussed in this post.
Dynamic Programming Approach: In this article, we are discussing a Dynamic Programming based solution.
Follow the steps below to solve the problem:
- Utmost min (N, X) elements can be selected from A[]and min(N, Y) elements can be selected from B[].
- Initialize a 2D array dp[][] such that dp[i][j] contains the maximum sum possible by selecting i elements from A[] and j elements from B[] where i and j range within min (N, X) and min (N, X) respectively.
- Initialize a variable max_sum to store the maximum sum possible.
- Traverse the array and for every array, element do the following:
- The (i + j)th element can either be A[i + j – 1] or B[i + j – 1].
- If the (i + j)th element is selected from A[], then the cost of (i + 1)th element in A[] will be added to the total cost. Hence, the cost of selecting (i + 1)th element is dp[i][j] = dp[ i – 1 ][ j ] + A[ i + j – 1 ] for this case.
- If the (i + j)th element is selected from B[], then the cost of selecting (i + 1)th element is dp[i][j] = dp[ i – 1 ][ j ] + B[ i + j – 1 ].
- Now, the target is to maximize the cost. Hence, the recurrence relation is:
dp[i][j] = max(dp[ i – 1 ][ j ] + A[ i + j – 1 ], dp[ i – 1 ][ j ] + B[ i + j – 1 ])
- Keep updating max_sum after every iteration. After complete traversal of the array print the final value of max_sum.
Below is the implementation of the above approach :
C++
// C++ program to find maximum sum// possible by selecting an element// from one of two arrays for every index#include <bits/stdc++.h>using namespace std;// Function to calculate maximum sumint maximumSum(int A[], int B[], int length, int X, int Y){ int l = length; // Maximum elements that can be // chosen from array A int l1 = min(length, X); // Maximum elements that can be // chosen from array B int l2 = min(length, Y); int dp[l1 + 1][l2 + 1]; memset(dp, 0, sizeof(dp)); dp[0][0] = 0; // Stores the maximum // sum possible int max_sum = INT_MIN; // Fill the dp[][] for base case when // all elements are selected from A[] for (int i = 1; i <= l1; i++) { dp[i][0] = dp[i - 1][0] + A[i - 1]; max_sum = max(max_sum, dp[i][0]); } // Fill the dp[][] for base case when // all elements are selected from B[] for (int i = 1; i <= l2; i++) { dp[0][i] = dp[0][i - 1] + B[i - 1]; max_sum = max(max_sum, dp[0][i]); } for (int i = 1; i <= l1; i++) { for (int j = 1; j <= l2; j++) { if (i + j <= l) dp[i][j] = max(dp[i - 1][j] + A[i + j - 1], dp[i][j - 1] + B[i + j - 1]); max_sum = max(dp[i][j], max_sum); } } // Return the final answer return max_sum;}// Driver Programint main(){ int A[] = { 1, 2, 3, 4, 5 }; int B[] = { 5, 4, 3, 2, 1 }; int X = 3, Y = 2; int N = sizeof(A) / sizeof(A[0]); cout << maximumSum(A, B, N, X, Y); return 0;} |
Java
// Java program to find maximum sum // possible by selecting an element // from one of two arrays for every index class GFG{ // Function to calculate maximum sumstatic int maximumSum(int A[], int B[], int length, int X, int Y){ int l = length; // Maximum elements that can be // chosen from array A int l1 = Math.min(length, X); // Maximum elements that can be // chosen from array B int l2 = Math.min(length, Y); int dp[][] = new int [l1 + 1][l2 + 1]; // Stores the maximum // sum possible int max_sum = Integer.MIN_VALUE; // Fill the dp[][] for base case when // all elements are selected from A[] for(int i = 1; i <= l1; i++) { dp[i][0] = dp[i - 1][0] + A[i - 1]; max_sum = Math.max(max_sum, dp[i][0]); } // Fill the dp[][] for base case when // all elements are selected from B[] for(int i = 1; i <= l2; i++) { dp[0][i] = dp[0][i - 1] + B[i - 1]; max_sum = Math.max(max_sum, dp[0][i]); } for(int i = 1; i <= l1; i++) { for(int j = 1; j <= l2; j++) { if (i + j <= l) dp[i][j] = Math.max(dp[i - 1][j] + A[i + j - 1], dp[i][j - 1] + B[i + j - 1]); max_sum = Math.max(dp[i][j], max_sum); } } // Return the final answer return max_sum;} // Driver code public static void main (String[] args) { int A[] = new int[]{ 1, 2, 3, 4, 5 }; int B[] = new int[]{ 5, 4, 3, 2, 1 }; int X = 3, Y = 2; int N = A.length; System.out.println(maximumSum(A, B, N, X, Y));} } // This code is contributed by Pratima Pandey |
Python
# Python3 program to find maximum sum# possible by selecting an element# from one of two arrays for every index# Function to calculate maximum sumdef maximumSum(A, B, length, X, Y): l = length # Maximum elements that can be # chosen from array A l1 = min(length, X) # Maximum elements that can be # chosen from array B l2 = min(length, Y) dp=[[ 0 for i in range(l2 + 1)] for i in range(l1 + 1)] dp[0][0] = 0 # Stores the maximum # sum possible max_sum = -10 * 9 # Fill the dp[]for base case when # all elements are selected from A[] for i in range(1, l1 + 1): dp[i][0] = dp[i - 1][0] + A[i - 1] max_sum = max(max_sum, dp[i][0]) # Fill the dp[]for base case when # all elements are selected from B[] for i in range(1, l2 + 1): dp[0][i] = dp[0][i - 1] + B[i - 1] max_sum = max(max_sum, dp[0][i]) for i in range(1, l1 + 1): for j in range(1, l2 + 1): if (i + j <= l): dp[i][j]= max(dp[i - 1][j] + A[i + j - 1], dp[i][j - 1] + B[i + j - 1]) max_sum = max(dp[i][j], max_sum) # Return the final answer return max_sum# Driver Programif __name__ == '__main__': A= [1, 2, 3, 4, 5] B= [5, 4, 3, 2, 1] X = 3 Y = 2 N = len(A) print(maximumSum(A, B, N, X, Y))# This code is contributed by Mohit Kumar 29 |
C#
// C# program to find maximum sum // possible by selecting an element // from one of two arrays for every index using System;class GFG{ // Function to calculate maximum sumstatic int maximumSum(int []A, int []B, int length, int X, int Y){ int l = length; // Maximum elements that can be // chosen from array A int l1 = Math.Min(length, X); // Maximum elements that can be // chosen from array B int l2 = Math.Min(length, Y); int [,]dp = new int [l1 + 1, l2 + 1]; // Stores the maximum // sum possible int max_sum = int.MinValue; // Fill the [,]dp for base case when // all elements are selected from []A for(int i = 1; i <= l1; i++) { dp[i, 0] = dp[i - 1, 0] + A[i - 1]; max_sum = Math.Max(max_sum, dp[i, 0]); } // Fill the [,]dp for base case when // all elements are selected from []B for(int i = 1; i <= l2; i++) { dp[0, i] = dp[0, i - 1] + B[i - 1]; max_sum = Math.Max(max_sum, dp[0, i]); } for(int i = 1; i <= l1; i++) { for(int j = 1; j <= l2; j++) { if (i + j <= l) dp[i, j] = Math.Max(dp[i - 1, j] + A[i + j - 1], dp[i, j - 1] + B[i + j - 1]); max_sum = Math.Max(dp[i, j], max_sum); } } // Return the readonly answer return max_sum;} // Driver code public static void Main(String[] args) { int []A = new int[]{ 1, 2, 3, 4, 5 }; int []B = new int[]{ 5, 4, 3, 2, 1 }; int X = 3, Y = 2; int N = A.Length; Console.WriteLine(maximumSum(A, B, N, X, Y));} } // This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program to find maximum sum// possible by selecting an element// from one of two arrays for every index// Function to calculate maximum sumfunction maximumSum(A, B, length, X, Y){ var l = length; // Maximum elements that can be // chosen from array A var l1 = Math.min(length, X); // Maximum elements that can be // chosen from array B var l2 = Math.min(length, Y); var dp = Array.from(Array(l1+1), ()=> Array(l2+1).fill(0)); dp[0][0] = 0; // Stores the maximum // sum possible var max_sum = -1000000000; // Fill the dp[][] for base case when // all elements are selected from A[] for (var i = 1; i <= l1; i++) { dp[i][0] = dp[i - 1][0] + A[i - 1]; max_sum = Math.max(max_sum, dp[i][0]); } // Fill the dp[][] for base case when // all elements are selected from B[] for (var i = 1; i <= l2; i++) { dp[0][i] = dp[0][i - 1] + B[i - 1]; max_sum = Math.max(max_sum, dp[0][i]); } for (var i = 1; i <= l1; i++) { for (var j = 1; j <= l2; j++) { if (i + j <= l) dp[i][j] = Math.max(dp[i - 1][j] + A[i + j - 1], dp[i][j - 1] + B[i + j - 1]); max_sum = Math.max(dp[i][j], max_sum); } } // Return the final answer return max_sum;}// Driver Programvar A = [ 1, 2, 3, 4, 5 ];var B = [ 5, 4, 3, 2, 1 ];var X = 3, Y = 2;var N = A.length;document.write( maximumSum(A, B, N, X, Y));</script> |
Output:
21
Time Complexity: O(N2)
Auxiliary Space: O(N2)
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!
