Given an array arr[ ] consisting of N integers, the task is to find maximum difference between the sum of two subsets obtained by partitioning the array into any two non-empty subsets.
Note: The subsets cannot any common element. A subset can contain repeating elements.
Examples:
Input: arr[] = {1, 3, 2, 4, 5}
Output: 13
Explanation: The partitions {3, 2, 4, 5} and {1} maximizes the difference between the subsets.Input: arr[] = {1, -5, 3, 2, -7}
Output: 18
Explanation: The partitions {1, 3, 2} and {-5, -7} maximizes the difference between the subsets.
Approach: This problem can be solved using greedy approach. In this problem both the subsets A and B must be non-empty. So we have to put at least one element in both of them. We try to make sum of elements in subset A as greater as possible and sum of elements in subset B as smaller as possible. Finally we print sum(A) – sum(B).
Follow the steps given below to solve the problem:
- When arr[ ] contains both non-negative and negative numbers, put all non-negative numbers in subset A and negative numbers in subset B, and print sum(A) – sum(B).
- When all numbers are positive, put all numbers in subset A except the smallest positive number put that in subset B, and print sum(A) – sum(B).
- When all numbers are negative, put all numbers in subset B except the largest negative put that in subset A, and print sum(A) – sum(B).
Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;int maxSumAfterPartition(int arr[], int n){ // Stores the positive elements vector<int> pos; // Stores the negative elements vector<int> neg; // Stores the count of 0s int zero = 0; // Sum of all positive numbers int pos_sum = 0; // Sum of all negative numbers int neg_sum = 0; // Iterate over the array for (int i = 0; i < n; i++) { if (arr[i] > 0) { pos.push_back(arr[i]); pos_sum += arr[i]; } else if (arr[i] < 0) { neg.push_back(arr[i]); neg_sum += arr[i]; } else { zero++; } } // Stores the difference int ans = 0; // Sort the positive numbers // in ascending order sort(pos.begin(), pos.end()); // Sort the negative numbers // in decreasing order sort(neg.begin(), neg.end(), greater<int>()); // Case 1: Include both positive // and negative numbers if (pos.size() > 0 && neg.size() > 0) { ans = (pos_sum - neg_sum); } else if (pos.size() > 0) { if (zero > 0) { // Case 2: When all numbers are // positive and array contains 0s //Put all numbers in subset A and //one 0 in subset B ans = (pos_sum); } else { // Case 3: When all numbers are positive //Put all numbers in subset A except the //smallest positive number which is put in B ans = (pos_sum - 2 * pos[0]); } } else { if (zero > 0) { // Case 4: When all numbers are // negative and array contains 0s // Put all numbers in subset B // and one 0 in subset A ans = (-1 * neg_sum); } else { // Case 5: When all numbers are negative // Place the largest negative number // in subset A and remaining in B ans = (neg[0] - (neg_sum - neg[0])); } } return ans;}int main(){ int arr[] = { 1, 2, 3, -5, -7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << maxSumAfterPartition(arr, n); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { static int maxSumAfterPartition(int arr[], int n) { // Stores the positive elements ArrayList<Integer> pos = new ArrayList<Integer>(); // Stores the negative elements ArrayList<Integer> neg = new ArrayList<Integer>(); // Stores the count of 0s int zero = 0; // Sum of all positive numbers int pos_sum = 0; // Sum of all negative numbers int neg_sum = 0; // Iterate over the array for (int i = 0; i < n; i++) { if (arr[i] > 0) { pos.add(arr[i]); pos_sum += arr[i]; } else if (arr[i] < 0) { neg.add(arr[i]); neg_sum += arr[i]; } else { zero++; } } // Stores the difference int ans = 0; // Sort the positive numbers // in ascending order Collections.sort(pos); // Sort the negative numbers // in decreasing order Collections.sort(neg); // Case 1: Include both positive // and negative numbers if (pos.size() > 0 && neg.size() > 0) { ans = (pos_sum - neg_sum); } else if (pos.size() > 0) { if (zero > 0) { // Case 2: When all numbers are // positive and array contains 0s // Put all numbers in subset A and // one 0 in subset B ans = (pos_sum); } else { // Case 3: When all numbers are positive // Put all numbers in subset A except the // smallest positive number which is put in // B ans = (pos_sum - 2 * pos.get(0)); } } else { if (zero > 0) { // Case 4: When all numbers are // negative and array contains 0s // Put all numbers in subset B // and one 0 in subset A ans = (-1 * neg_sum); } else { // Case 5: When all numbers are negative // Place the largest negative number // in subset A and remaining in B ans = (neg.get(0) - (neg_sum - neg.get(0))); } } return ans; } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 3, -5, -7 }; int n = 5; System.out.println(maxSumAfterPartition(arr, n)); }}// This code is contributed by maddler. |
Python3
# Python 3 Program for the above approachdef maxSumAfterPartition(arr, n): # Stores the positive elements pos = [] # Stores the negative elements neg = [] # Stores the count of 0s zero = 0 # Sum of all positive numbers pos_sum = 0 # Sum of all negative numbers neg_sum = 0 # Iterate over the array for i in range(n): if (arr[i] > 0): pos.append(arr[i]) pos_sum += arr[i] elif(arr[i] < 0): neg.append(arr[i]) neg_sum += arr[i] else: zero += 1 # Stores the difference ans = 0 # Sort the positive numbers # in ascending order pos.sort() # Sort the negative numbers # in decreasing order neg.sort(reverse=True) # Case 1: Include both positive # and negative numbers if (len(pos) > 0 and len(neg) > 0): ans = (pos_sum - neg_sum) elif(len(pos) > 0): if (zero > 0): # Case 2: When all numbers are # positive and array contains 0s #Put all numbers in subset A and #one 0 in subset B ans = (pos_sum) else: # Case 3: When all numbers are positive #Put all numbers in subset A except the #smallest positive number which is put in B ans = (pos_sum - 2 * pos[0]) else: if (zero > 0): # Case 4: When all numbers are # negative and array contains 0s # Put all numbers in subset B # and one 0 in subset A ans = (-1 * neg_sum) else: # Case 5: When all numbers are negative # Place the largest negative number # in subset A and remaining in B ans = (neg[0] - (neg_sum - neg[0])) return ansif __name__ == '__main__': arr = [1, 2, 3, -5, -7] n = len(arr) print(maxSumAfterPartition(arr, n)) # This code is contributed by ipg2016107. |
C#
// C# Program for the above approachusing System;using System.Collections.Generic;class GFG{static int maxSumAfterPartition(int []arr, int n){ // Stores the positive elements List<int> pos = new List<int>(); // Stores the negative elements List<int> neg = new List<int>(); // Stores the count of 0s int zero = 0; // Sum of all positive numbers int pos_sum = 0; // Sum of all negative numbers int neg_sum = 0; // Iterate over the array for (int i = 0; i < n; i++) { if (arr[i] > 0) { pos.Add(arr[i]); pos_sum += arr[i]; } else if (arr[i] < 0) { neg.Add(arr[i]); neg_sum += arr[i]; } else { zero++; } } // Stores the difference int ans = 0; // Sort the positive numbers // in ascending order pos.Sort(); // Sort the negative numbers // in decreasing order neg.Sort(); neg.Reverse(); // Case 1: Include both positive // and negative numbers if (pos.Count > 0 && neg.Count > 0) { ans = (pos_sum - neg_sum); } else if (pos.Count > 0) { if (zero > 0) { // Case 2: When all numbers are // positive and array contains 0s //Put all numbers in subset A and //one 0 in subset B ans = (pos_sum); } else { // Case 3: When all numbers are positive //Put all numbers in subset A except the //smallest positive number which is put in B ans = (pos_sum - 2 * pos[0]); } } else { if (zero > 0) { // Case 4: When all numbers are // negative and array contains 0s // Put all numbers in subset B // and one 0 in subset A ans = (-1 * neg_sum); } else { // Case 5: When all numbers are negative // Place the largest negative number // in subset A and remaining in B ans = (neg[0] - (neg_sum - neg[0])); } } return ans;}public static void Main(){ int []arr = { 1, 2, 3, -5, -7 }; int n = arr.Length; Console.Write(maxSumAfterPartition(arr, n));}}// This code is contributed by ipg2016107. |
Javascript
<script> // JavaScript Program to implement // the above approach function maxSumAfterPartition(arr, n) { // Stores the positive elements let pos = []; // Stores the negative elements let neg = []; // Stores the count of 0s let zero = 0; // Sum of all positive numbers let pos_sum = 0; // Sum of all negative numbers let neg_sum = 0; // Iterate over the array for (let i = 0; i < n; i++) { if (arr[i] > 0) { pos.push(arr[i]); pos_sum += arr[i]; } else if (arr[i] < 0) { neg.push(arr[i]); neg_sum += arr[i]; } else { zero++; } } // Stores the difference let ans = 0; // Sort the positive numbers // in ascending order pos.sort(function (a, b) { return a - b }) // Sort the negative numbers // in decreasing order neg.sort(function (a, b) { return b - a }) // Case 1: Include both positive // and negative numbers if (pos.length > 0 && neg.length > 0) { ans = (pos_sum - neg_sum); } else if (pos.length > 0) { if (zero > 0) { // Case 2: When all numbers are // positive and array contains 0s //Put all numbers in subset A and //one 0 in subset B ans = (pos_sum); } else { // Case 3: When all numbers are positive //Put all numbers in subset A except the //smallest positive number which is put in B ans = (pos_sum - 2 * pos[0]); } } else { if (zero > 0) { // Case 4: When all numbers are // negative and array contains 0s // Put all numbers in subset B // and one 0 in subset A ans = (-1 * neg_sum); } else { // Case 5: When all numbers are negative // Place the largest negative number // in subset A and remaining in B ans = (neg[0] - (neg_sum - neg[0])); } } return ans; } let arr = [1, 2, 3, -5, -7]; let n = arr.length; document.write(maxSumAfterPartition(arr, n));// This code is contributed by Potta Lokesh </script> |
Output
18
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
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!
