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 casesint 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 Codeint main(){ vector<int> A = { 1, 10, 4, -6, 3 }; cout << findBest(A) << endl; return 0;} |
Java
// Java Program to implement// the above approachimport 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 casesstatic 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 Codepublic 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 casesdef 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 Codeif __name__ == "__main__": A = [ 1, 10, 4, -6, 3 ] print (findBest(A))# This code is contributed by chitranayal |
C#
// C# Program to implement// the above approachusing System;class GFG{// Function returns maximum // subset sum from the given arraystatic 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 Codepublic 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 casesfunction 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!
