Maximize sum of subsets from two arrays having no consecutive values
Last Updated : 16 Oct, 2023
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]).
- 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 sum void 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 Code int 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 program for the above approach import 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); } } # Python program of the above approach # Function to calculate maximum subset sum def 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 arrays arr1 = [ -1, -2, 4, -4, 5 ] arr2 = [ -1, -2, -3, 4, 10 ] # Length of the array length = 5 maximumSubsetSum(arr1, arr2, length) # This code is contributed by susmitakundugoaldanga.
// C# program for the above approach using 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. <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> 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 sum void 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 Code int 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; } 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); } } 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 Code if __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)
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); } } 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); Time Complexity: O(N)
Auxiliary Space: O(1)
Similar Reads
Maximum sum of Subset having no consecutive elements Given an array arr[] of size N, the task is to find the maximum possible sum of a subset of the array such that no two consecutive elements are part of the subset. Examples: Input: arr[]= {2, 3, 2, 3, 3, 4}Output: 9Explanation: The subset having all the 3s i.e. {3, 3, 3} have sum = 9.This is the max
9 min read
Maximise the size of consecutive element subsets in an array Given an integer array and an integer k. The array elements denote positions of points on a 1-D number line, find the maximum size of the subset of points that can have consecutive values of points which can be formed by placing another k points on the number line. Note that all coordinates should b
12 min read
Maximize value of a pair from two given arrays based on given conditions Given two arrays A[] and B[] consisting of N integers and an integer K, the task is to find the maximum value of B[i] + B[j] + abs(A[i] - A[j]) by choosing any pair (i, j) such that abs(A[i] - A[j]) ? K. Examples: Input: A[] = {5, 6, 9, 10}, B[] = {3, 0, 10, -10}, K = 1Output: 4Explanation:Only two
15+ min read
Maximize sum of selected numbers from Array to empty it | Set 2 Given an array arr[] of N integers, the task is to maximize the sum of selected numbers over all the operations such that in each operation, choose a number Ai, delete one occurrence of it and delete all occurrences of Ai - 1 and Ai + 1 (if they exist) in the array until the array gets empty. Exampl
7 min read
Maximum subsequence sum such that no K elements are consecutive Given an array arr[] of N positive integers, the task is to find the maximum sum of a subsequence consisting of no K consecutive array elements. Examples: Input: arr[] = {10, 5, 8, 16, 21}, K = 4Output: 55Explanation:Maximum sum is obtained by picking 10, 8, 16, 21. Input: arr[] = {4, 12, 22, 18, 34
9 min read
Maximum consecutive numbers present in an array Find the length of maximum number of consecutive numbers jumbled up in an array.Examples: Input : arr[] = {1, 94, 93, 1000, 5, 92, 78};Output : 3 The largest set of consecutive elements is92, 93, 94 Input : arr[] = {1, 5, 92, 4, 78, 6, 7};Output : 4 The largest set of consecutive elements is4, 5, 6,
15+ min read