Given two arrays arr1[] and arr2[] of equal length, the task is to find the maximum sum of any subset possible by selecting elements from both the arrays such that no two elements in the subset should be consecutive.
Examples:
Input: arr1[] = {-1, -2, 4, -4, 5}, arr2[] = {-1, -2, -3, 4, 10}
Output: 14
Explanation:
Required subset {4, 10}. Therefore, sum = 4 + 10 = 14.Input: arr1[] = {2, 5, 4, 2000}, arr2[] = {-2000, 100, 23, 40}
Output: 2100
Naive Approach: The simplest approach is to generate all possible subsets from both the given arrays such that no two adjacent elements are consecutive and calculate the sum of each subset. Finally, print the maximum sum possible.
Time Complexity: O(N*2N)
Auxiliary Space: O(2N)
Efficient Approach: The above approach can be optimized using Dynamic Programming. Follow the steps below to solve the problem:
- Initialize an auxiliary array dp[] of size N.
- Here, dp[i] stores the maximum possible sum of a subset from both the arrays such that no two elements are consecutive.
- Declare a function maximumSubsetSum():
- Base Cases:
- dp[1] = max(arr1[1], arr2[1]).
- dp[2] = max(max(arr1[1], arr2[1]), max(arr1[2], arr2[2])).
- For all other cases, following three conditions arise:
- dp[i] = max(arr1[i], arr2[i], arr1[i] + dp[i – 2], arr2[i] + dp[i – 2], dp[i – 1]).
- Base Cases:
- Finally, print dp[N] as the required 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 calculate maximum subset sumvoid maximumSubsetSum(int arr1[],int arr2[], int length){ // Initialize array to store dp states int dp[length+1]; // Base Cases if (length == 1) { cout << (max(arr1[0], arr2[0])); return; } if (length == 2) { cout << (max(max(arr1[1], arr2[1]), max(arr1[0], arr2[0]))); return; } else { // Pre initializing for dp[0] & dp[1] dp[0] = max(arr1[0], arr2[0]); dp[1] = max(max(arr1[1], arr2[1]), max(arr1[0], arr2[0])); int index = 2; while (index < length) { // Calculating dp[index] based on // above formula dp[index] = max(max(arr1[index], arr2[index]), max(max(arr1[index] + dp[index - 2], arr2[index] + dp[index - 2]), dp[index - 1])); ++index; } // Print maximum subset sum cout<<(dp[length - 1]); }}// Driver Codeint main(){ // Given arrays int arr1[] = { -1, -2, 4, -4, 5 }; int arr2[] = { -1, -2, -3, 4, 10 }; // Length of the array int length = 5; maximumSubsetSum(arr1, arr2, length); return 0;}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to calculate maximum subset sum static void maximumSubsetSum(int arr1[], int arr2[], int length) { // Initialize array to store dp states int dp[] = new int[length + 1]; // Base Cases if (length == 1) { System.out.print( Math.max(arr1[0], arr2[0])); return; } if (length == 2) { System.out.print( Math.max( Math.max(arr1[1], arr2[1]), Math.max(arr1[0], arr2[0]))); return; } else { // Pre initializing for dp[0] & dp[1] dp[0] = Math.max(arr1[0], arr2[0]); dp[1] = Math.max( Math.max(arr1[1], arr2[1]), Math.max(arr1[0], arr2[0])); int index = 2; while (index < length) { // Calculating dp[index] based on // above formula dp[index] = Math.max( Math.max(arr1[index], arr2[index]), Math.max( Math.max( arr1[index] + dp[index - 2], arr2[index] + dp[index - 2]), dp[index - 1])); ++index; } // Print maximum subset sum System.out.print(dp[length - 1]); } } // Driver Code public static void main(String[] args) { // Given arrays int arr1[] = { -1, -2, 4, -4, 5 }; int arr2[] = { -1, -2, -3, 4, 10 }; // Length of the array int length = arr1.length; maximumSubsetSum(arr1, arr2, length); }} |
Python3
# Python program of the above approach# Function to calculate maximum subset sumdef maximumSubsetSum(arr1, arr2, length) : # Initialize array to store dp states dp = [0] * (length+1) # Base Cases if (length == 1) : print(max(arr1[0], arr2[0])) return if (length == 2) : print(max(max(arr1[1], arr2[1]), max(arr1[0], arr2[0]))) return else : # Pre initializing for dp[0] & dp[1] dp[0] = max(arr1[0], arr2[0]) dp[1] = max(max(arr1[1], arr2[1]), max(arr1[0], arr2[0])) index = 2 while (index < length) : # Calculating dp[index] based on # above formula dp[index] = max(max(arr1[index], arr2[index]), max(max(arr1[index] + dp[index - 2], arr2[index] + dp[index - 2]), dp[index - 1])) index += 1 # Print maximum subset sum print(dp[length - 1]) # Driver Code# Given arraysarr1 = [ -1, -2, 4, -4, 5 ]arr2 = [ -1, -2, -3, 4, 10 ]# Length of the arraylength = 5maximumSubsetSum(arr1, arr2, length)# This code is contributed by susmitakundugoaldanga. |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate maximum subset sum static void maximumSubsetSum(int[] arr1, int[] arr2, int length) { // Initialize array to store dp states int[] dp = new int[length + 1]; // Base Cases if (length == 1) { Console.WriteLine(Math.Max(arr1[0], arr2[0])); return; } if (length == 2) { Console.WriteLine(Math.Max( Math.Max(arr1[1], arr2[1]), Math.Max(arr1[0], arr2[0]))); return; } else { // Pre initializing for dp[0] & dp[1] dp[0] = Math.Max(arr1[0], arr2[0]); dp[1] = Math.Max(Math.Max(arr1[1], arr2[1]), Math.Max(arr1[0], arr2[0])); int index = 2; while (index < length) { // Calculating dp[index] based on // above formula dp[index] = Math.Max(Math.Max(arr1[index], arr2[index]), Math.Max(Math.Max(arr1[index] + dp[index - 2], arr2[index] + dp[index - 2]), dp[index - 1])); ++index; } // Print maximum subset sum Console.WriteLine(dp[length - 1]); } } // Driver Code static public void Main() { // Given arrays int[] arr1 = { -1, -2, 4, -4, 5 }; int[] arr2 = { -1, -2, -3, 4, 10 }; // Length of the array int length = arr1.Length; maximumSubsetSum(arr1, arr2, length); }}// This code is contributed by code_hunt. |
Javascript
<script>// javascript program of the above approach // Function to calculate maximum subset sum function maximumSubsetSum(arr1, arr2,length) { // Initialize array to store dp states let dp = new Array(length).fill(0);; // Base Cases if (length == 1) { document.write( Math.max(arr1[0], arr2[0])); return; } if (length == 2) { document.write( Math.max( Math.max(arr1[1], arr2[1]), Math.max(arr1[0], arr2[0]))); return; } else { // Pre initializing for dp[0] & dp[1] dp[0] = Math.max(arr1[0], arr2[0]); dp[1] = Math.max( Math.max(arr1[1], arr2[1]), Math.max(arr1[0], arr2[0])); let index = 2; while (index < length) { // Calculating dp[index] based on // above formula dp[index] = Math.max( Math.max(arr1[index], arr2[index]), Math.max( Math.max( arr1[index] + dp[index - 2], arr2[index] + dp[index - 2]), dp[index - 1])); ++index; } // Print maximum subset sum document.write(dp[length - 1]); } } // Driver Code // Given arrays let arr1 = [ -1, -2, 4, -4, 5 ]; let arr2 = [ -1, -2, -3, 4, 10 ]; // Length of the array let length = arr1.length; maximumSubsetSum(arr1, arr2, length);</script> |
Output
14
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach : Space optimization O(1)
In previous approach we the current value dp[i] is only depend upon the previous 2 values i.e. dp[i-1] and dp[i-2]. So to optimize the space we can keep track of previous and current values by the help of three variables prev1, prev2 and curr which will reduce the space complexity from O(x) to O(1).
Implementation:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate maximum subset sumvoid maximumSubsetSum(int arr1[],int arr2[], int length){ // Initialize variables to store dp states int dp0 = max(arr1[0], arr2[0]); int dp1 = max(max(arr1[1], arr2[1]), max(arr1[0], arr2[0])); int dpi = dp1, dpim2 = dp0; // Base Cases if (length == 1) { cout << dp0; return; } if (length == 2) { cout << dp1; return; } else { int index = 2; while (index < length) { // Calculating dp[index] based on above formula dpi = max(max(arr1[index], arr2[index]), max(max(arr1[index] + dpim2, arr2[index] + dpim2), dp1)); dpim2 = dp1; dp1 = dpi; ++index; } // Print maximum subset sum cout<<(dpi); }}// Driver Codeint main(){ // Given arrays int arr1[] = { -1, -2, 4, -4, 5 }; int arr2[] = { -1, -2, -3, 4, 10 }; // Length of the array int length = 5; maximumSubsetSum(arr1, arr2, length); return 0;} |
Java
public class GFG { // Function to calculate maximum subset sum static void maximumSubsetSum(int[] arr1, int[] arr2, int length) { // Initialize variables to store dp states int dp0 = Math.max(arr1[0], arr2[0]); int dp1 = Math.max(Math.max(arr1[1], arr2[1]), Math.max(arr1[0], arr2[0])); int dpi = dp1, dpim2 = dp0; // Base Cases if (length == 1) { System.out.println(dp0); return; } if (length == 2) { System.out.println(dp1); return; } else { int index = 2; while (index < length) { // Calculating dp[index] based on the formula dpi = Math.max(Math.max(arr1[index], arr2[index]), Math.max(Math.max(arr1[index] + dpim2, arr2[index] + dpim2), dp1)); dpim2 = dp1; dp1 = dpi; ++index; } // Print maximum subset sum System.out.println(dpi); } } // Driver Code public static void main(String[] args) { // Given arrays int[] arr1 = { -1, -2, 4, -4, 5 }; int[] arr2 = { -1, -2, -3, 4, 10 }; // Length of the array int length = 5; maximumSubsetSum(arr1, arr2, length); }} |
Python3
def maximumSubsetSum(arr1, arr2, length): # Initialize variables to store dp states dp0 = max(arr1[0], arr2[0]) dp1 = max(max(arr1[1], arr2[1]), max(arr1[0], arr2[0])) dpi, dpim2 = dp1, dp0 # Base Cases if length == 1: print(dp0) return if length == 2: print(dp1) return else: index = 2 while index < length: # Calculating dpi based on the given formula dpi = max( max(arr1[index], arr2[index]), max( max(arr1[index] + dpim2, arr2[index] + dpim2), dp1 ) ) dpim2 = dp1 dp1 = dpi index += 1 # Print maximum subset sum print(dpi)# Driver Codeif __name__ == "__main__": # Given arrays arr1 = [-1, -2, 4, -4, 5] arr2 = [-1, -2, -3, 4, 10] # Length of the array length = 5 maximumSubsetSum(arr1, arr2, length) |
C#
using System;class Program{ static void MaximumSubsetSum(int[] arr1, int[] arr2, int length) { // Initialize variables to store dp states int dp0 = Math.Max(arr1[0], arr2[0]); int dp1 = Math.Max(Math.Max(arr1[1], arr2[1]), Math.Max(arr1[0], arr2[0])); int dpi = dp1, dpim2 = dp0; // Base Cases if (length == 1) { Console.Write(dp0); return; } if (length == 2) { Console.Write(dp1); return; } else { int index = 2; while (index < length) { // Calculating dp[index] based on above formula dpi = Math.Max(Math.Max(arr1[index], arr2[index]), Math.Max(Math.Max(arr1[index] + dpim2, arr2[index] + dpim2), dp1)); dpim2 = dp1; dp1 = dpi; ++index; } Console.Write(dpi); } } static void Main(string[] args) { int[] arr1 = { -1, -2, 4, -4, 5 }; int[] arr2 = { -1, -2, -3, 4, 10 }; int length = 5; MaximumSubsetSum(arr1, arr2, length); }} |
Javascript
function maximumSubsetSum(arr1, arr2, length) { // Initialize variables to store dp states let dp0 = Math.max(arr1[0], arr2[0]); let dp1 = Math.max(Math.max(arr1[1], arr2[1]), Math.max(arr1[0], arr2[0])); let dpi = dp1; let dpim2 = dp0; // Base Cases if (length === 1) { console.log(dp0); // Print the maximum subset sum return; } if (length === 2) { console.log(dp1); // Print the maximum subset sum return; } else { let index = 2; while (index < length) { // Calculate dpi based on the maximum of different cases dpi = Math.max( Math.max(arr1[index], arr2[index]), Math.max( Math.max(arr1[index] + dpim2, arr2[index] + dpim2), dp1 ) ); dpim2 = dp1; dp1 = dpi; index++; } console.log(dpi); // Print the maximum subset sum }}const arr1 = [-1, -2, 4, -4, 5];const arr2 = [-1, -2, -3, 4, 10];const length = 5;maximumSubsetSum(arr1, arr2, length); |
Output
14
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!
