Given an of integers of size N. The task is to separate these integers into two groups g1 and g2 such that (sum of elements of g1) – (sum of elements of g2) becomes maximum. Your task is to print the value of result. We may keep one subset as empty.
Examples:
Input : 3, 7, -4, 10, -11, 2
Output : 37
Explanation:
g1: 3, 7, 10, 2
g2: -4, -11
result = ( 3 + 7 + 10 + 2 ) – ( -4 + -11) = 22 – (-15) = 37Input : 2, 2, -2, -2
Output : 8
The idea is to group integers according to their sign value i.e., we group positive integers as g1 and negative integers as g2.
Since, – ( -g2 ) = +g2
Therefore, result becomes g1 + |g2|.
C++
// CPP program to make two subsets with // maximum difference. #include <bits/stdc++.h> using namespace std; int maxDiff( int arr[], int n) { int sum = 0; // We move all negative elements into // one set. So we add negation of negative // numbers to maximize difference for ( int i = 0; i < n; i++) sum = sum + abs (arr[i]); return sum; } // Driver Code int main() { int arr[] = { 3, 7, -4, 10, -11, 2 }; int n = sizeof (arr)/ sizeof (arr[0]); cout << maxDiff(arr, n); return 0; } |
Java
// Java program to make two subsets with // maximum difference. import java.util.*; class solution { static int maxDiff( int arr[], int n) { int sum = 0 ; // We move all negative elements into // one set. So we add negation of negative // numbers to maximize difference for ( int i = 0 ; i < n; i++) sum = sum + Math.abs(arr[i]); return sum; } // Driver Code public static void main(String args[]) { int []arr = { 3 , 7 , - 4 , 10 , - 11 , 2 }; int n = arr.length; System.out.println(maxDiff(arr, n)); } } |
Python3
# Python3 program to make two subsets # with maximum difference. def maxDiff(arr, n) : sum = 0 # We move all negative elements into # one set. So we add negation of negative # numbers to maximize difference for i in range (n) : sum + = abs (arr[i]) return sum # Driver Code if __name__ = = "__main__" : arr = [ 3 , 7 , - 4 , 10 , - 11 , 2 ] n = len (arr) print (maxDiff(arr, n)) # This code is contributed by Ryuga |
C#
using System; // C# program to make two subsets with // maximum difference. public class solution { public static int maxDiff( int [] arr, int n) { int sum = 0; // We move all negative elements into // one set. So we add negation of negative // numbers to maximize difference for ( int i = 0; i < n; i++) { sum = sum + Math.Abs(arr[i]); } return sum; } // Driver Code public static void Main( string [] args) { int [] arr = new int [] {3, 7, -4, 10, -11, 2}; int n = arr.Length; Console.WriteLine(maxDiff(arr, n)); } } // This code is contributed by Shrikant13 |
PHP
<?php // PHP program to make two subsets // with maximum difference. function maxDiff( $arr , $n ) { $sum = 0; // We move all negative elements // into one set. So we add negation // of negative numbers to maximize // difference for ( $i = 0; $i < $n ; $i ++) $sum = $sum + abs ( $arr [ $i ]); return $sum ; } // Driver Code $arr = array ( 3, 7, -4, 10, -11, 2 ); $n = sizeof( $arr ); echo maxDiff( $arr , $n ); // This code is contributed by Sachin. ?> |
Javascript
<script> // javascript program to make two subsets with // maximum difference. function maxDiff(arr , n) { var sum = 0; // We move all negative elements into // one set. So we add negation of negative // numbers to maximize difference for (i = 0; i < n; i++) sum = sum + Math.abs(arr[i]); return sum; } // Driver Code var arr = [ 3, 7, -4, 10, -11, 2 ]; var n = arr.length; document.write(maxDiff(arr, n)); // This code is contributed by Princi Singh </script> |
37
Time Complexity: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!