Maximum sum by picking elements from two arrays in order | Set 2

0 0 8 minutes read

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 sum
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 = 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 Program
int 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 sum
static 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 sum
def 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 Program
if __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 sum
static 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 sum
function 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 Program
var 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:

Time Complexity: O(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 zambiatek!