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 Codeint 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 Codepublic 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 Codevar arr = [ 3, 7, -4, 10, -11, 2 ];var n = arr.length;document.write(maxDiff(arr, n));// This code is contributed by Princi Singh </script> |
Output
37
Time Complexity: 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!
