Given an array A containing N elements. Partition any subset of this array into two disjoint subsets such that both the subsets have an identical sum. Obtain the maximum sum that can be obtained after partitioning.
Note: It is not necessary to partition the entire array, that is any element might not contribute to any of the partition.
Examples:
Input: A = [1, 2, 3, 6]
Output: 6
Explanation: We have two disjoint subsets {1, 2, 3} and {6}, which have the same sum = 6Input: A = [1, 2, 3, 4, 5, 6]
Output: 10
Explanation: We have two disjoint subsets {2, 3, 5} and {4, 6}, which have the same sum = 10.Input: A = [1, 2]
Output: 0
Explanation: No subset can be partitioned into 2 disjoint subsets with identical sum
Naive Approach:
The above problem can be solved by brute force method using recursion. All the elements have three possibilities. Either it will contribute to partition 1 or partition 2 or will not be included in any of the partitions. We will perform these three operations on each of the elements and proceed to the next element in each recursive step.
Below is the implementation of the above approach:
C++
// CPP implementation for the// above mentioned recursive approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum subset sumint maxSum(int p0, int p1, int a[], int pos, int n){ if (pos == n) { if (p0 == p1) return p0; else return 0; } // Ignore the current element int ans = maxSum(p0, p1, a, pos + 1, n); // including element in partition 1 ans = max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n)); // including element in partition 2 ans = max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n)); return ans;}// Driver codeint main(){ // size of the array int n = 4; int a[n] = { 1, 2, 3, 6 }; cout << maxSum(0, 0, a, 0, n); return 0;} |
Java
// Java implementation for the// above mentioned recursive approachclass GFG { // Function to find the maximum subset sum static int maxSum(int p0, int p1, int a[], int pos, int n) { if (pos == n) { if (p0 == p1) return p0; else return 0; } // Ignore the current element int ans = maxSum(p0, p1, a, pos + 1, n); // including element in partition 1 ans = Math.max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n)); // including element in partition 2 ans = Math.max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n)); return ans; } // Driver code public static void main (String[] args) { // size of the array int n = 4; int a[] = { 1, 2, 3, 6 }; System.out.println(maxSum(0, 0, a, 0, n)); }}// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation for the# above mentioned recursive approach# Function to find the maximum subset sumdef maxSum(p0, p1, a, pos, n) : if (pos == n) : if (p0 == p1) : return p0; else : return 0; # Ignore the current element ans = maxSum(p0, p1, a, pos + 1, n); # including element in partition 1 ans = max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n)); # including element in partition 2 ans = max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n)); return ans;# Driver codeif __name__ == "__main__" : # size of the array n = 4; a = [ 1, 2, 3, 6 ]; print(maxSum(0, 0, a, 0, n));# This code is contributed by AnkitRai01 |
C#
// C# implementation for the// above mentioned recursive approachusing System;public class GFG { // Function to find the maximum subset sum static int maxSum(int p0, int p1, int []a, int pos, int n) { if (pos == n) { if (p0 == p1) return p0; else return 0; } // Ignore the current element int ans = maxSum(p0, p1, a, pos + 1, n); // including element in partition 1 ans = Math.Max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n)); // including element in partition 2 ans = Math.Max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n)); return ans; } // Driver code public static void Main (string[] args) { // size of the array int n = 4; int []a = { 1, 2, 3, 6 }; Console.WriteLine(maxSum(0, 0, a, 0, n)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation for the// above mentioned recursive approach// Function to find the maximum subset sumfunction maxSum(p0, p1, a, pos, n){ if (pos == n) { if (p0 == p1) return p0; else return 0; } // Ignore the current element var ans = maxSum(p0, p1, a, pos + 1, n); // Including element in partition 1 ans = Math.max(ans, maxSum( p0 + a[pos], p1, a, pos + 1, n)); // Including element in partition 2 ans = Math.max(ans, maxSum( p0, p1 + a[pos], a, pos + 1, n)); return ans;}// Driver code// Size of the arrayvar n = 4;var a = [ 1, 2, 3, 6 ];document.write(maxSum(0, 0, a, 0, n));// This code is contributed by importantly</script> |
Output
6
Time Complexity: 
Auxiliary Space: O(n)
Memoization: Aa we can see there are multiple overlapping subproblems so instead of solving them again and again we can store each recursive call result in an array and use it .
C++
// CPP implementation for the// above mentioned recursive approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum subset sumint maxSum(int p0, int p1, int a[], int pos, int n, vector<vector<int> >& dp){ if (pos == n) { if (p0 == p1) return p0; else return 0; } //if the value is already computed then return that previous computed value. if (dp[pos][p0] != -1) { return dp[pos][p0]; } // Ignore the current element int ans = maxSum(p0, p1, a, pos + 1, n, dp); // including element in partition 1 ans = max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n, dp)); // including element in partition 2 ans = max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n, dp)); return dp[pos][p0] = ans;}int maxSum(int p0, int p1, int a[], int pos, int n){ int sum = 0; for (int i = 0; i < n; i++) { sum += a[i]; } vector<vector<int> > dp(n, vector<int>(sum + 1, -1)); return maxSum(p0, p1, a, pos, n, dp);}// Driver codeint main(){ // size of the array int n = 4; int a[n] = { 1, 2, 3, 6 }; cout << maxSum(0, 0, a, 0, n); return 0;} |
Java
// Java implementation for the// above mentioned recursive approachimport java.util.Arrays;class GFG { // Function to find the maximum subset sum static int maxSum(int p0, int p1, int a[], int pos, int n, int[][] dp) { if (pos == n) { if (p0 == p1) return p0; else return 0; } //if the value is already computed then return that previous computed value. if (dp[pos][p0] != -1) { return dp[pos][p0]; } // Ignore the current element int ans = maxSum(p0, p1, a, pos + 1, n, dp); // including element in partition 1 ans = Math.max( ans, maxSum(p0 + a[pos], p1, a, pos + 1, n,dp)); // including element in partition 2 ans = Math.max( ans, maxSum(p0, p1 + a[pos], a, pos + 1, n,dp)); return dp[pos][p0] = ans; } static int maxSum(int p0, int p1, int a[], int pos, int n) { int sum = 0; for (int i = 0; i < n; i++) { sum += a[i]; } int dp[][] = new int[n][sum + 1]; for (int row[] : dp) { Arrays.fill(row, -1); } return maxSum(p0, p1, a, pos, n, dp); } // Driver code public static void main(String[] args) { // size of the array int n = 4; int a[] = { 1, 2, 3, 6 }; System.out.println(maxSum(0, 0, a, 0, n)); }} |
Python3
# Python code for the above approachdef maxSum(p0, p1, a, pos, n, dp): # Base case : If we have reached the end of the array if pos == n: # If both partitions have equal sum, return that sum if p0 == p1: return p0 # If both partitions have different sum, return 0 else: return 0 # If the value is already computed, return that previous computed value if dp[pos][p0] != -1: return dp[pos][p0] # Ignore the current element ans = maxSum(p0, p1, a, pos + 1, n, dp) # including element in partition 1 ans = max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n, dp)) # including element in partition 2 ans = max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n, dp)) dp[pos][p0] = ans return dp[pos][p0]def maxSumWrapper(a,n): sum = 0 for i in range(n): sum += a[i] dp = [[-1 for i in range(sum+1)] for j in range(n)] return maxSum(0, 0, a, 0, n, dp)# Driver codeif __name__ == '__main__': # size of the array n = 4 a = [1, 2, 3, 6] print(maxSumWrapper(a, n)) # This code is contributed by pradeepkumarppk2003 |
C#
// C# implementation for the// above mentioned recursive approachusing System;class GFG{ // Function to find the maximum subset sum static int maxSum(int p0, int p1, int[] a, int pos, int n, int[,] dp) { if (pos == n) { if (p0 == p1) return p0; else return 0; } //if the value is already computed then return // that previous computed value. if (dp[pos, p0] != -1) { return dp[pos, p0]; } // Ignore the current element int ans = maxSum(p0, p1, a, pos + 1, n, dp); // including element in partition 1 ans = Math.Max( ans, maxSum(p0 + a[pos], p1, a, pos + 1, n, dp)); // including element in partition 2 ans = Math.Max( ans, maxSum(p0, p1 + a[pos], a, pos + 1, n, dp)); return dp[pos, p0] = ans; } static int maxSum(int p0, int p1, int[] a, int pos, int n) { int sum = 0; for (int i = 0; i < n; i++) { sum += a[i]; } int[,] dp = new int[n, sum + 1]; for (int i = 0; i < n; i++) { for (int j = 0; j < sum + 1; j++) { dp[i, j] = -1; } } return maxSum(p0, p1, a, pos, n, dp); } // Driver code public static void Main(string[] args) { // size of the array int n = 4; int[] a = { 1, 2, 3, 6 }; Console.WriteLine(maxSum(0, 0, a, 0, n)); }}//This code is contributed by ik_9 |
Javascript
// Javascript implementation for the// above mentioned recursive approach// Function to find the maximum subset sumfunction maxSum(p0, p1, a, pos, n, dp) { if (pos == n) { if (p0 == p1) return p0; else return 0; } //if the value is already computed then return that previous computed value. if (dp[pos][p0] != -1) { return dp[pos][p0]; } // Ignore the current element let ans = maxSum(p0, p1, a, pos + 1, n, dp); // including element in partition 1 ans = Math.max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n, dp)); // including element in partition 2 ans = Math.max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n, dp)); return dp[pos][p0] = ans;}function maxsum(p0, p1, a, pos, n) { let sum = 0; for (let i = 0; i < n; i++) { sum += a[i]; } let dp=new Array(n); for(let i=0;i<n;i++) { dp[i]=new Array(sum+1); for(let j=0;j<sum+1;j++) dp[i][j]=-1; } return maxSum(p0, p1, a, pos, n, dp);}// Driver code// size of the arraylet n = 4;let a = [1, 2, 3, 6];console.log(maxsum(0, 0, a, 0, n)); |
Output
6
Time Complexity: O(N*Sum), where Sum represents sum of all array elements.
Auxiliary Space: O(N*Sum) + O(N) .
Efficient Approach:
The above method can be optimized using Dynamic Programming method.
We will define our DP state as follows :
dp[i][j] = Max sum of group g0 considering the first i elements such that,
the difference between the sum of g0 and g1 is (sum of all elements – j), where j is the difference.
So, the answer would be dp[n][sum]
Now we might encounter, the difference between the sums is negative, lying in the range [-sum, +sum], where the sum is a summation of all elements. The minimum and maximum ranges occurring when one of the subsets is empty and the other one has all the elements. Due to this, in the DP state, we have defined j as (sum – diff). Thus, j will range from [0, 2*sum].
Below is the implementation of the above approach:
C++
// CPP implementation for the above mentioned// Dynamic Programming approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum subset sumint maxSum(int a[], int n){ // sum of all elements int sum = 0; for (int i = 0; i < n; i++) sum += a[i]; int limit = 2 * sum + 1; // bottom up lookup table; int dp[n + 1][limit]; // initialising dp table with INT_MIN // where, INT_MIN means no solution for (int i = 0; i < n + 1; i++) { for (int j = 0; j < limit; j++) dp[i][j] = INT_MIN; } // Case when diff is 0 dp[0][sum] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < limit; j++) { // Putting ith element in g0 if ((j - a[i - 1]) >= 0 && dp[i - 1][j - a[i - 1]] != INT_MIN) dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i - 1]] + a[i - 1]); // Putting ith element in g1 if ((j + a[i - 1]) < limit && dp[i - 1][j + a[i - 1]] != INT_MIN) dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i - 1]]); // Ignoring ith element if (dp[i - 1][j] != INT_MIN) dp[i][j] = max(dp[i][j], dp[i - 1][j]); } } return dp[n][sum];}// Driver codeint main(){ int n = 4; int a[n] = { 1, 2, 3, 6 }; cout << maxSum(a, n); return 0;} |
Java
// Java implementation for the above mentioned // Dynamic Programming approach class GFG { final static int INT_MIN = Integer.MIN_VALUE; // Function to find the maximum subset sum static int maxSum(int a[], int n) { // sum of all elements int sum = 0; for (int i = 0; i < n; i++) sum += a[i]; int limit = 2 * sum + 1; // bottom up lookup table; int dp[][] = new int[n + 1][limit]; // initialising dp table with INT_MIN // where, INT_MIN means no solution for (int i = 0; i < n + 1; i++) { for (int j = 0; j < limit; j++) dp[i][j] = INT_MIN; } // Case when diff is 0 dp[0][sum] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < limit; j++) { // Putting ith element in g0 if ((j - a[i - 1]) >= 0 && dp[i - 1][j - a[i - 1]] != INT_MIN) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - a[i - 1]] + a[i - 1]); // Putting ith element in g1 if ((j + a[i - 1]) < limit && dp[i - 1][j + a[i - 1]] != INT_MIN) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + a[i - 1]]); // Ignoring ith element if (dp[i - 1][j] != INT_MIN) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]); } } return dp[n][sum]; } // Driver code public static void main (String[] args) { int n = 4; int []a = { 1, 2, 3, 6 }; System.out.println(maxSum(a, n)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation for the above mentioned # Dynamic Programming approach import numpy as npimport sysINT_MIN = -(sys.maxsize - 1)# Function to find the maximum subset sum def maxSum(a, n) : # sum of all elements sum = 0; for i in range(n) : sum += a[i]; limit = 2 * sum + 1; # bottom up lookup table; dp = np.zeros((n + 1,limit)); # initialising dp table with INT_MIN # where, INT_MIN means no solution for i in range(n + 1) : for j in range(limit) : dp[i][j] = INT_MIN; # Case when diff is 0 dp[0][sum] = 0; for i in range(1, n + 1) : for j in range(limit) : # Putting ith element in g0 if ((j - a[i - 1]) >= 0 and dp[i - 1][j - a[i - 1]] != INT_MIN) : dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i - 1]] + a[i - 1]); # Putting ith element in g1 if ((j + a[i - 1]) < limit and dp[i - 1][j + a[i - 1]] != INT_MIN) : dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i - 1]]); # Ignoring ith element if (dp[i - 1][j] != INT_MIN) : dp[i][j] = max(dp[i][j], dp[i - 1][j]); return dp[n][sum]; # Driver code if __name__ == "__main__" : n = 4; a = [ 1, 2, 3, 6 ]; print(maxSum(a, n)); # This code is contributed by Yash_R |
C#
// C# implementation for the above mentioned // Dynamic Programming approach using System;class GFG { static int INT_MIN = int.MinValue; // Function to find the maximum subset sum static int maxSum(int []a, int n) { // sum of all elements int sum = 0; for (int i = 0; i < n; i++) sum += a[i]; int limit = 2 * sum + 1; // bottom up lookup table; int [,]dp = new int[n + 1,limit]; // initialising dp table with INT_MIN // where, INT_MIN means no solution for (int i = 0; i < n + 1; i++) { for (int j = 0; j < limit; j++) dp[i,j] = INT_MIN; } // Case when diff is 0 dp[0,sum] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < limit; j++) { // Putting ith element in g0 if ((j - a[i - 1]) >= 0 && dp[i - 1,j - a[i - 1]] != INT_MIN) dp[i,j] = Math.Max(dp[i,j], dp[i - 1,j - a[i - 1]] + a[i - 1]); // Putting ith element in g1 if ((j + a[i - 1]) < limit && dp[i - 1,j + a[i - 1]] != INT_MIN) dp[i,j] = Math.Max(dp[i,j], dp[i - 1,j + a[i - 1]]); // Ignoring ith element if (dp[i - 1,j] != INT_MIN) dp[i,j] = Math.Max(dp[i,j], dp[i - 1,j]); } } return dp[n,sum]; } // Driver code public static void Main() { int n = 4; int []a = { 1, 2, 3, 6 }; Console.WriteLine(maxSum(a, n)); } }// This code is contributed by Yash_R |
Javascript
<script>// JavaScript implementation for the above mentioned// Dynamic Programming approach// Function to find the maximum subset sumfunction maxSum(a, n){ // sum of all elements var sum = 0; for (var i = 0; i < n; i++) sum += a[i]; var limit = 2 * sum + 1; // bottom up lookup table; var dp = Array.from(Array(n+1), ()=>Array(limit)); // initialising dp table with -1000000000 // where, -1000000000 means no solution for (var i = 0; i < n + 1; i++) { for (var j = 0; j < limit; j++) dp[i][j] = -1000000000; } // Case when diff is 0 dp[0][sum] = 0; for (var i = 1; i <= n; i++) { for (var j = 0; j < limit; j++) { // Putting ith element in g0 if ((j - a[i - 1]) >= 0 && dp[i - 1][j - a[i - 1]] != -1000000000) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - a[i - 1]] + a[i - 1]); // Putting ith element in g1 if ((j + a[i - 1]) < limit && dp[i - 1][j + a[i - 1]] != -1000000000) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + a[i - 1]]); // Ignoring ith element if (dp[i - 1][j] != -1000000000) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]); } } return dp[n][sum];}// Driver codevar n = 4;var a = [1, 2, 3, 6];document.write( maxSum(a, n));</script> |
Output
6
Time Complexity: 
, where Sum represents sum of all array elements.
Auxiliary Space:
Efficient Approach : using array instead of 2d matrix to optimize space complexity
In previous code we can se that dp[i][j] is dependent upon dp[i-1] or dp[i] so we can assume that dp[i-1] is previous row and dp[i] is current row.
Implementations Steps :
- Create two vectors prev and curr each of size limit+1, where limit is a 2 * sum + 1.
- Initialize them with base cases.
- Now In previous code change dp[i] to curr and change dp[i-1] to prev to keep track only of the two main rows.
- After every iteration update previous row to current row to iterate further.
Implementation :
C++
// CPP implementation for the above mentioned// Dynamic Programming approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum subset sumint maxSum(int a[], int n){ // sum of all elements int sum = 0; for (int i = 0; i < n; i++) sum += a[i]; int limit = 2 * sum + 1; // initialising curr and prev vectors table with INT_MIN // where, INT_MIN means no solution vector<int>prev(limit +1 , INT_MIN); vector<int>curr(limit +1 , INT_MIN); // Case when diff is 0 prev[sum] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < limit; j++) { // Putting ith element in g0 if ((j - a[i - 1]) >= 0 && prev[j - a[i - 1]] != INT_MIN) curr[j] = max(curr[j], prev[j - a[i - 1]] + a[i - 1]); // Putting ith element in g1 if ((j + a[i - 1]) < limit && prev[j + a[i - 1]] != INT_MIN) curr[j] = max(curr[j], prev[j + a[i - 1]]); // Ignoring ith element if (prev[j] != INT_MIN) curr[j] = max(curr[j], prev[j]); } // assigning values of curr to prev vector to iterate further prev = curr; } // return answer return curr[sum];}// Driver codeint main(){ int n = 4; int a[n] = { 1, 2, 3, 6 }; // function call cout << maxSum(a, n); return 0;} |
Java
// Java implementation for the above approach// Dynamic Programming approachimport java.util.*;public class Main { // Function to find the maximum subset sum public static int maxSum(int[] a, int n) { // sum of all elements int sum = 0; for (int i = 0; i < n; i++) sum += a[i]; int limit = 2 * sum + 1; // initialising curr and prev vectors table with // INT_MIN where, INT_MIN means no solution int[] prev = new int[limit + 1]; int[] curr = new int[limit + 1]; Arrays.fill(prev, Integer.MIN_VALUE); Arrays.fill(curr, Integer.MIN_VALUE); // Case when diff is 0 prev[sum] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < limit; j++) { // Putting ith element in g0 if ((j - a[i - 1]) >= 0 && prev[j - a[i - 1]] != Integer.MIN_VALUE) curr[j] = Math.max(curr[j], prev[j - a[i - 1]] + a[i - 1]); // Putting ith element in g1 if ((j + a[i - 1]) < limit && prev[j + a[i - 1]] != Integer.MIN_VALUE) curr[j] = Math.max(curr[j], prev[j + a[i - 1]]); // Ignoring ith element if (prev[j] != Integer.MIN_VALUE) curr[j] = Math.max(curr[j], prev[j]); } // assigning values of curr to prev vector to // iterate further prev = curr.clone(); } // return answer return curr[sum]; } // Driver code public static void main(String[] args) { int n = 4; int[] a = { 1, 2, 3, 6 }; // function call System.out.println(maxSum(a, n)); }}// This code is contributed by sarojmcy2e |
Python
def max_sum(a, n): # Sum of all elements total_sum = sum(a) # Calculate the limit for the array limit = 2 * total_sum + 1 # Initialize curr and prev lists with float('-inf') prev = [float('-inf')] * (limit + 1) curr = [float('-inf')] * (limit + 1) # Case when diff is 0 prev[total_sum] = 0 for i in range(1, n + 1): for j in range(limit): # Putting the ith element in group 0 if (j - a[i - 1]) >= 0 and prev[j - a[i - 1]] != float('-inf'): curr[j] = max(curr[j], prev[j - a[i - 1]] + a[i - 1]) # Putting the ith element in group 1 if (j + a[i - 1]) < limit and prev[j + a[i - 1]] != float('-inf'): curr[j] = max(curr[j], prev[j + a[i - 1]]) # Ignoring the ith element if prev[j] != float('-inf'): curr[j] = max(curr[j], prev[j]) # Assigning values of curr to prev list to iterate further prev = curr[:] # Return the answer return curr[total_sum]# Driver codeif __name__ == "__main__": n = 4 a = [1, 2, 3, 6] # Function call print(max_sum(a, n)) |
C#
// C# implementation for the above mentioned// Dynamic Programming approachusing System;using System.Collections.Generic;class GFG { // Function to find the maximum subset sum static int MaxSum(int[] a, int n) { // sum of all elements int sum = 0; for (int i = 0; i < n; i++) sum += a[i]; int limit = 2 * sum + 1; // initialising curr and prev vectors table with INT_MIN // where, INT_MIN means no solution List<int> prev = new List<int>(); List<int> curr = new List<int>(); for (int i = 0; i <= limit; i++) { prev.Add(int.MinValue); curr.Add(int.MinValue); } // Case when diff is 0 prev[sum] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < limit; j++) { // Putting ith element in g0 if ((j - a[i - 1]) >= 0 && prev[j - a[i - 1]] != int.MinValue) curr[j] = Math.Max(curr[j], prev[j - a[i - 1]] + a[i - 1]); // Putting ith element in g1 if ((j + a[i - 1]) < limit && prev[j + a[i - 1]] != int.MinValue) curr[j] = Math.Max(curr[j], prev[j + a[i - 1]]); // Ignoring ith element if (prev[j] != int.MinValue) curr[j] = Math.Max(curr[j], prev[j]); } // assigning values of curr to prev vector to iterate further prev = new List<int>(curr); } // return answer return curr[sum]; } // Driver code static void Main(string[] args) { int n = 4; int[] a = { 1, 2, 3, 6 }; // function call Console.WriteLine(MaxSum(a, n)); }}// This code is contributed by Vaibhav Nandan |
Javascript
function maxSum(a, n) { // sum of all elements let sum = 0; for (let i = 0; i < n; i++) sum += a[i]; let limit = 2 * sum + 1; // initialising curr and prev vectors table with INT_MIN // where, INT_MIN means no solution let prev = new Array(limit + 1).fill(Number.MIN_SAFE_INTEGER); let curr = new Array(limit + 1).fill(Number.MIN_SAFE_INTEGER); // Case when diff is 0 prev[sum] = 0; for (let i = 1; i <= n; i++) { for (let j = 0; j < limit; j++) { // Putting ith element in g0 if ((j - a[i - 1]) >= 0 && prev[j - a[i - 1]] != Number.MIN_SAFE_INTEGER) curr[j] = Math.max(curr[j], prev[j - a[i - 1]] + a[i - 1]); // Putting ith element in g1 if ((j + a[i - 1]) < limit && prev[j + a[i - 1]] != Number.MIN_SAFE_INTEGER) curr[j] = Math.max(curr[j], prev[j + a[i - 1]]); // Ignoring ith element if (prev[j] != Number.MIN_SAFE_INTEGER) curr[j] = Math.max(curr[j], prev[j]); } // assigning values of curr to prev vector to iterate further prev = [...curr]; } // return answer return curr[sum];}// Driver codelet n = 4;let a = [1, 2, 3, 6];// function callconsole.log(maxSum(a, n)); |
Output:
6
Time Complexity: O(N*Sum)
Auxiliary Space: O(Sum)
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!
