Given an array A[] consisting of N integers, the task is to find the maximum subset-sum possible if the sum of all the elements is negated if the first element of the array is included. An empty subset(having sum 0) can also be considered.
Examples:
Input: N = 5, A[] = {1, 10, 4, -6, 3}
Output: 17
Explanation:
On excluding A[0], subset with maximum sum = {10, 4, 3}, Sum = (10+4+3) = 17
On including A[0], subset with maximum sum = {1, -6}, Sum = (1 + (-6)) = -5, on negating -(-5) = 5
Maximum of the above two sum is max(17, 5) = 17
Input: N = 4, A[] = {3, -5, 1, -6}
Output: 8
Explanation:
On excluding A[0], subset with maximum sum = {1}, Sum = 1
On including A[0], subset with maximum sum = {3, -5, -6}, Sum = (3 + (-5) + (-6)) = -8, on negating -(-8) = 8
Maximum of the above two sum is max(1, 8) = 8
Naive Approach:
The simplest approach to solve the problem is to generate all possible subsets from the array and find the maximum subset-sum maxSum and the minimum subset-sum minSum by including the first element as a part of every subset. Finally, print the maximum of maxSum and -(minSum).
Time Complexity: O(2N)
Auxiliary Space: O(N)
Efficient Approach:
To optimize the above approach, consider the following two cases:
- The first element is excluded, simply find the sum (say maxSum1) of all positive integers from the given array.
- Negate all the elements except A[0] and find the sum (say maxSum2) of all positive integers from the array and then negate it and add A[0] to the sum.
- Print the maximum of maxSum1 and -maxSum2 as the required answer.
Detailed steps for each case are listed below:
Case 1: Excluding the first element A[0]
- Iterate from A[1] to A[N-1].
- Maintain a variable maxSum1, to keep track of maximum sum, initially set to 0.
- If a positive element (A[i] > 0) is encountered, include it in the subset, and maxSum1 will be (maxSum1 + A[i]).
- In the end, return the maxSum1.
Case 2: Including the first element A[0]
- Since on including the first element entire sum will be negated, find the minimum sum possible excluding A[0].
- A minimum sum can be achieved using the same steps done in Case 1, but with negative values.
- Negate all the values from A[1] to A[N-1].
- Perform the same steps as in Case 1.
- Once the sum is obtained(say maxSum2), negate it and add A[0] to it.
- Negate maxSum2 again.
In the end, maximum(maxSum1, maxsum2) will be the required answer.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function returns maximum subset sum // from the given array= int maxSubset(vector< int >& A, bool flag) { int n = A.size(); int sum = 0; // Case 2: Negate values // from A[1] to A[N-1] if (flag) { for ( int i = 1; i < n; i++) A[i] = -A[i]; } for ( int i = 1; i < n; i++) { // Include only positives // for max subset sum if (A[i] > 0) { sum += A[i]; } } // Return max sum obtained return sum; } // Function to return maximum of the // maximum subset sum calculated // for the two cases int findBest(vector< int > A) { // Case 1 int x = maxSubset(A, 0); // Case 2 int y = maxSubset(A, 1); // Modifying the sum y = -y; // Including first element y += A[0]; // Negating again y = -y; // Return the required answer return max(x, y); } // Driver Code int main() { vector< int > A = { 1, 10, 4, -6, 3 }; cout << findBest(A) << endl; return 0; } |
Java
// Java Program to implement // the above approach import java.util.*; class GFG{ // Function returns maximum subset sum // from the given array= static int maxSubset( int []A, boolean flag) { int n = A.length; int sum = 0 ; // Case 2: Negate values // from A[1] to A[N-1] if (flag) { for ( int i = 1 ; i < n; i++) A[i] = -A[i]; } for ( int i = 1 ; i < n; i++) { // Include only positives // for max subset sum if (A[i] > 0 ) { sum += A[i]; } } // Return max sum obtained return sum; } // Function to return maximum of the // maximum subset sum calculated // for the two cases static int findBest( int []A) { // Case 1 int x = maxSubset(A, false ); // Case 2 int y = maxSubset(A, true ); // Modifying the sum y = -y; // Including first element y += A[ 0 ]; // Negating again y = -y; // Return the required answer return Math.max(x, y); } // Driver Code public static void main(String[] args) { int []A = { 1 , 10 , 4 , - 6 , 3 }; System.out.print(findBest(A) + "\n" ); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement # the above approach # Function returns maximum subset # sum from the given array= def maxSubset(A, flag): n = len (A) sum = 0 ; # Case 2: Negate values # from A[1] to A[N-1] if (flag): for i in range ( 1 , n): A[i] = - A[i] for i in range ( 1 , n): # Include only positives # for max subset sum if (A[i] > 0 ): sum + = A[i] # Return max sum obtained return sum # Function to return maximum of the # maximum subset sum calculated # for the two cases def findBest(A): # Case 1 x = maxSubset(A, 0 ) # Case 2 y = maxSubset(A, 1 ) # Modifying the sum y = - y # Including first element y + = A[ 0 ] # Negating again y = - y # Return the required answer return max (x, y) # Driver Code if __name__ = = "__main__" : A = [ 1 , 10 , 4 , - 6 , 3 ] print (findBest(A)) # This code is contributed by chitranayal |
C#
// C# Program to implement // the above approach using System; class GFG{ // Function returns maximum // subset sum from the given array static int maxSubset( int []A, bool flag) { int n = A.Length; int sum = 0; // Case 2: Negate values // from A[1] to A[N-1] if (flag) { for ( int i = 1; i < n; i++) A[i] = -A[i]; } for ( int i = 1; i < n; i++) { // Include only positives // for max subset sum if (A[i] > 0) { sum += A[i]; } } // Return max sum obtained return sum; } // Function to return maximum of the // maximum subset sum calculated // for the two cases static int findBest( int []A) { // Case 1 int x = maxSubset(A, false ); // Case 2 int y = maxSubset(A, true ); // Modifying the sum y = -y; // Including first element y += A[0]; // Negating again y = -y; // Return the required answer return Math.Max(x, y); } // Driver Code public static void Main(String[] args) { int []A = {1, 10, 4, -6, 3}; Console.Write(findBest(A) + "\n" ); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function returns maximum subset sum // from the given array= function maxSubset(A, flag) { let n = A.length; let sum = 0; // Case 2: Negate values // from A[1] to A[N-1] if (flag) { for (let i = 1; i < n; i++) A[i] = -A[i]; } for (let i = 1; i < n; i++) { // Include only positives // for max subset sum if (A[i] > 0) { sum += A[i]; } } // Return max sum obtained return sum; } // Function to return maximum of the // maximum subset sum calculated // for the two cases function findBest(A) { // Case 1 let x = maxSubset(A, false ); // Case 2 let y = maxSubset(A, true ); // Modifying the sum y = -y; // Including first element y += A[0]; // Negating again y = -y; // Return the required answer return Math.max(x, y); } // Driver Code let A = [ 1, 10, 4, -6, 3 ]; document.write(findBest(A) + "\n" ); </script> |
17
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!