Given two arrays A[] and B[] each of size N, the task is to find the maximum sum that can be obtained based on the following conditions:
- Both A[i] and B[i] cannot be included in the sum ( 0 ? i ? N – 1 ).
- If B[i] is added to the sum, then B[i – 1] and A[i – 1] cannot be included in the sum ( 0 ? i ? N – 1 ).
Examples:
Input: A[] = {10, 20, 5}, B[] = {5, 5, 45}
Output: 55
Explanation: The optimal way to maximize the sum is by including A[0] (= 10) and B[2] (= 45) in the sum. Therefore, sum = 10 + 45 = 55.Input: A[] = {10, 1, 10, 10}, B[] = {5, 50, 1, 5}
Output: 70
Approach: This problem has Optimal substructure and Overlapping subproblems. Therefore, Dynamic Programming can be used to solve the problem.
Follow the steps below to solve the problem:
- Initialize a array, say dp[n][2], where dp[i][0] stores the maximum sum if element A[i] is taken into consideration and dp[i][1] stores the maximum sum if B[i] is taken into consideration.
- Iterate in the range [0, N – 1] using a variable, say i, and perform the following steps:
- If i is equal to 0, then modify the value of dp[i][0] as A[i] and dp[i][1] as B[i].
- Otherwise, perform the following operations:
- Modify the value of dp[i][0] as max(dp[i – 1][0], dp[i – 1][1]) + A[i].
- Modify the value of dp[i][1] as max(dp[i – 1], max(dp[i – 1][0], max(dp[i – 2][0], dp[i – 2][1]) + B[i])).
- After completing the above steps, print the max(dp[N-1][0], dp[N-1][1]) as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum// that can be obtained from two given// based on the following conditionsint MaximumSum(int a[], int b[], int n){ // Stores the maximum // sum from 0 to i int dp[n][2]; // Initialize the value of // dp[0][0] and dp[0][1] dp[0][0] = a[0]; dp[0][1] = b[0]; // Traverse the array A[] and B[] for (int i = 1; i < n; i++) { // If A[i] is considered dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + a[i]; // If B[i] is not considered dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]); // If B[i] is considered if (i - 2 >= 0) { dp[i][1] = max(dp[i][1], max(dp[i - 2][0], dp[i - 2][1]) + b[i]); } else { // If i = 1, then consider the // value of dp[i][1] as b[i] dp[i][1] = max(dp[i][1], b[i]); } } // Return maximum Sum return max(dp[n - 1][0], dp[n - 1][1]);}// Driver Codeint main(){ // Given Input int A[] = { 10, 1, 10, 10 }; int B[] = { 5, 50, 1, 5 }; int N = sizeof(A) / sizeof(A[0]); // Function Call cout << MaximumSum(A, B, N); return 0;} |
Java
// Java program for the above approachclass GFG { // Function to find the maximum sum // that can be obtained from two given // based on the following conditions public static int MaximumSum(int a[], int b[], int n) { // Stores the maximum // sum from 0 to i int[][] dp = new int[n][2]; // Initialize the value of // dp[0][0] and dp[0][1] dp[0][0] = a[0]; dp[0][1] = b[0]; // Traverse the array A[] and B[] for (int i = 1; i < n; i++) { // If A[i] is considered dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]) + a[i]; // If B[i] is not considered dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]); // If B[i] is considered if (i - 2 >= 0) { dp[i][1] = Math.max(dp[i][1], Math.max(dp[i - 2][0], dp[i - 2][1]) + b[i]); } else { // If i = 1, then consider the // value of dp[i][1] as b[i] dp[i][1] = Math.max(dp[i][1], b[i]); } } // Return maximum Sum return Math.max(dp[n - 1][0], dp[n - 1][1]); } // Driver Code public static void main(String args[]) { // Given Input int A[] = { 10, 1, 10, 10 }; int B[] = { 5, 50, 1, 5 }; int N = A.length; // Function Call System.out.println(MaximumSum(A, B, N)); }}// This code is contributed by _saurabh_jaiswal. |
Python3
# Python3 program for the above approach# Function to find the maximum sum# that can be obtained from two given# arrays based on the following conditionsdef MaximumSum(a, b, n): # Stores the maximum # sum from 0 to i dp = [[-1 for j in range(2)] for i in range(n)] # Initialize the value of # dp[0][0] and dp[0][1] dp[0][0] = a[0] dp[0][1] = b[0] # Traverse the array A[] and B[] for i in range(1, n): # If A[i] is considered dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + a[i] # If B[i] is not considered dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) # If B[i] is considered if (i - 2 >= 0): dp[i][1] = max(dp[i][1], max(dp[i - 2][0], dp[i - 2][1]) + b[i]) else: # If i = 1, then consider the # value of dp[i][1] as b[i] dp[i][1] = max(dp[i][1], b[i]) # Return maximum sum return max(dp[n - 1][0], dp[n - 1][1])# Driver codeif __name__ == '__main__': # Given input A = [ 10, 1, 10, 10 ] B = [ 5, 50, 1, 5 ] N = len(A) # Function call print(MaximumSum(A, B, N)) # This code is contributed by MuskanKalra1 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the maximum sum// that can be obtained from two given// based on the following conditionsstatic int MaximumSum(int []a, int []b, int n){ // Stores the maximum // sum from 0 to i int [,]dp = new int[n,2]; // Initialize the value of // dp[0][0] and dp[0][1] dp[0,0] = a[0]; dp[0,1] = b[0]; // Traverse the array A[] and B[] for (int i = 1; i < n; i++) { // If A[i] is considered dp[i,0] = Math.Max(dp[i - 1,0], dp[i - 1,1]) + a[i]; // If B[i] is not considered dp[i,1] = Math.Max(dp[i - 1,0], dp[i - 1,1]); // If B[i] is considered if (i - 2 >= 0) { dp[i,1] = Math.Max(dp[i,1], Math.Max(dp[i - 2,0], dp[i - 2,1]) + b[i]); } else { // If i = 1, then consider the // value of dp[i][1] as b[i] dp[i,1] = Math.Max(dp[i,1], b[i]); } } // Return maximum Sum return Math.Max(dp[n - 1,0], dp[n - 1,1]);}// Driver Codepublic static void Main(){ // Given Input int []A = { 10, 1, 10, 10 }; int []B = { 5, 50, 1, 5 }; int N = A.Length; // Function Call Console.Write(MaximumSum(A, B, N));}}// This code is contributed by ipg2016107. |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum sum// that can be obtained from two given// based on the following conditionsfunction MaximumSum(a, b, n) { // Stores the maximum // sum from 0 to i let dp = new Array(n).fill(0).map( () => new Array(2)); // Initialize the value of // dp[0][0] and dp[0][1] dp[0][0] = a[0]; dp[0][1] = b[0]; // Traverse the array A[] and B[] for(let i = 1; i < n; i++) { // If A[i] is considered dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]) + a[i]; // If B[i] is not considered dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]); // If B[i] is considered if (i - 2 >= 0) { dp[i][1] = Math.max(dp[i][1], Math.max(dp[i - 2][0], dp[i - 2][1]) + b[i]); } else { // If i = 1, then consider the // value of dp[i][1] as b[i] dp[i][1] = Math.max(dp[i][1], b[i]); } } // Return maximum Sum return Math.max(dp[n - 1][0], dp[n - 1][1]);}// Driver Code// Given Inputlet A = [ 10, 1, 10, 10 ];let B = [ 5, 50, 1, 5 ];let N = A.length;// Function Calldocument.write(MaximumSum(A, B, N));// This code is contributed by gfgking</script> |
Output
70
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach – Space optimization: In the previous approach, the current value dp[i] is only dependent upon the just previous values i.e., dp[i – 1]. So to optimize the space we can keep track of previous and current values with the help of variables prev_max_a, prev_max_b and curr_max_a, curr_max_b which will reduce the space complexity from O(N) to O(1). Below are the steps:
- Create variables prev_max_a and prev_max_b to keep track of previous values of DP.
- Initialize base case prev_max_a = a[0] , prev_max_b = b[0].
- Create a variable curr_max_a and curr_max_b to store the current value.
- Iterate over the subproblem using loop and update curr_max_a and curr_max_b and after every iteration, update prev_max_a and prev_max_b for further iterations.
- After the above steps, print the maximum of curr_max_a and curr_max_b.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum// that can be obtained from two given// based on the following conditionsint MaximumSum(int a[], int b[], int n){ int prev_max_a = a[0], curr_max_a = 0; int prev_max_b = b[0], curr_max_b = 0; // Traverse the array A[] and B[] for (int i = 1; i < n; i++) { // If A[i] is considered curr_max_a = max(prev_max_a, prev_max_b) + a[i]; // If B[i] is not considered curr_max_b = max(prev_max_a, prev_max_b); // If B[i] is considered if (i - 2 >= 0) { curr_max_b = max(curr_max_b, max(prev_max_a, prev_max_b) + b[i]); } // If i = 1, then consider the // value of dp[i][1] as b[i] else { curr_max_b = max(curr_max_b, b[i]); } // assigning values to iterate further prev_max_a = curr_max_a; prev_max_b = curr_max_b; } // Return maximum Sum return max(curr_max_a, curr_max_b);}// Driver Codeint main(){ // Given Input int A[] = { 10, 1, 10, 10 }; int B[] = { 5, 50, 1, 5 }; int N = sizeof(A) / sizeof(A[0]); // Function Call cout << MaximumSum(A, B, N); return 0;}// --- by bhardwajji |
Java
import java.util.*;public class MaximumSumTwoArrays { public static int maximumSum(int[] a, int[] b, int n) { int prevMaxA = a[0]; int currMaxA = 0; int prevMaxB = b[0]; int currMaxB = 0; for (int i = 1; i < n; i++) { // If A[i] is considered currMaxA = Math.max(prevMaxA, prevMaxB) + a[i]; // If B[i] is not considered currMaxB = Math.max(prevMaxA, prevMaxB); // If B[i] is considered if (i - 2 >= 0) { currMaxB = Math.max(currMaxB, Math.max(prevMaxA, prevMaxB) + b[i]); } else { // If i = 1, then consider the value of b[i] currMaxB = Math.max(currMaxB, b[i]); } // Assigning values to iterate further prevMaxA = currMaxA; prevMaxB = currMaxB; } // Return maximum sum return Math.max(currMaxA, currMaxB); } public static void main(String[] args) { // Given Input int[] A = { 10, 1, 10, 10 }; int[] B = { 5, 50, 1, 5 }; int N = A.length; // Function Call System.out.println(maximumSum(A, B, N)); }} |
Python
# Python program for the above approach# Function to find the maximum sum# that can be obtained from two given# based on the following conditionsdef MaximumSum(a, b, n): prev_max_a = a[0] curr_max_a = 0 prev_max_b = b[0] curr_max_b = 0 # Traverse the array A[] and B[] for i in range(1, n): # If A[i] is considered curr_max_a = max(prev_max_a, prev_max_b) + a[i] # If B[i] is not considered curr_max_b = max(prev_max_a, prev_max_b) # If B[i] is considered if i - 2 >= 0: curr_max_b = max(curr_max_b, max(prev_max_a, prev_max_b) + b[i]) # If i = 1, then consider the # value of dp[i][1] as b[i] else: curr_max_b = max(curr_max_b, b[i]) # assigning values to iterate further prev_max_a = curr_max_a prev_max_b = curr_max_b # Return maximum Sum return max(curr_max_a, curr_max_b)# Driver Codeif __name__ == '__main__': # Given Input A = [10, 1, 10, 10] B = [5, 50, 1, 5] N = len(A) # Function Call print(MaximumSum(A, B, N)) |
C#
using System;class Program { // Function to find the maximum sum // that can be obtained from two given // arrays based on the following conditions static int MaximumSum(int[] a, int[] b, int n) { int prevMaxA = a[0], currMaxA = 0; int prevMaxB = b[0], currMaxB = 0; // Traverse the arrays A[] and B[] for (int i = 1; i < n; i++) { // If A[i] is considered currMaxA = Math.Max(prevMaxA, prevMaxB) + a[i]; // If B[i] is not considered currMaxB = Math.Max(prevMaxA, prevMaxB); // If B[i] is considered if (i - 2 >= 0) { currMaxB = Math.Max( currMaxB, Math.Max(prevMaxA, prevMaxB) + b[i]); } // If i = 1, then consider the // value of dp[i][1] as b[i] else { currMaxB = Math.Max(currMaxB, b[i]); } // Assigning values to iterate further prevMaxA = currMaxA; prevMaxB = currMaxB; } // Return maximum Sum return Math.Max(currMaxA, currMaxB); } // Driver Code static void Main() { // Given Input int[] A = { 10, 1, 10, 10 }; int[] B = { 5, 50, 1, 5 }; int N = A.Length; // Function Call Console.WriteLine(MaximumSum(A, B, N)); }} |
Javascript
// Function to find the maximum sum// that can be obtained from two given// based on the following conditionsfunction MaximumSum(a, b, n) { let prev_max_a = a[0]; let curr_max_a = 0; let prev_max_b = b[0]; let curr_max_b = 0; // Traverse the array A[] and B[] for (let i = 1; i < n; i++) { // If A[i] is considered curr_max_a = Math.max(prev_max_a, prev_max_b) + a[i]; // If B[i] is not considered curr_max_b = Math.max(prev_max_a, prev_max_b); // If B[i] is considered if (i - 2 >= 0) { curr_max_b = Math.max(curr_max_b, Math.max(prev_max_a, prev_max_b) + b[i]); } // If i = 1, then consider the // value of dp[i][1] as b[i] else { curr_max_b = Math.max(curr_max_b, b[i]); } // assigning values to iterate further prev_max_a = curr_max_a; prev_max_b = curr_max_b; } // Return maximum Sum return Math.max(curr_max_a, curr_max_b);}// Given Inputconst A = [10, 1, 10, 10];const B = [5, 50, 1, 5];const N = A.length;// Function Callconsole.log(MaximumSum(A, B, N)); |
Output
70
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
