Dada una array arr[ ] que consta de N enteros, la tarea es encontrar la diferencia máxima entre la suma de dos subconjuntos obtenidos al dividir la array en dos subconjuntos no vacíos cualesquiera.
Nota: Los subconjuntos no pueden tener ningún elemento común. Un subconjunto puede contener elementos repetidos.
Ejemplos:
Entrada: arr[] = {1, 3, 2, 4, 5}
Salida: 13
Explicación: Las particiones {3, 2, 4, 5} y {1} maximizan la diferencia entre los subconjuntos.Entrada: arr[] = {1, -5, 3, 2, -7}
Salida: 18
Explicación : las particiones {1, 3, 2} y {-5, -7} maximizan la diferencia entre los subconjuntos.
Enfoque: este problema se puede resolver utilizando un enfoque codicioso . En este problema, los subconjuntos A y B no deben estar vacíos. Así que tenemos que poner al menos un elemento en ambos. Intentamos que la suma de los elementos del subconjunto A sea lo más grande posible y la suma de los elementos del subconjunto B lo más pequeña posible. Finalmente imprimimos sum(A) – sum(B).
Siga los pasos que se indican a continuación para resolver el problema:
- Cuando arr[ ] contiene números no negativos y negativos, coloque todos los números no negativos en el subconjunto A y los números negativos en el subconjunto B, e imprima sum(A) – sum(B) .
- Cuando todos los números sean positivos, coloque todos los números en el subconjunto A, excepto el número positivo más pequeño, colóquelo en el subconjunto B e imprima sum(A) – sum(B) .
- Cuando todos los números sean negativos, coloque todos los números en el subconjunto B, excepto el negativo más grande, colóquelo en el subconjunto A e imprima sum(A) – sum(B).
A continuación se muestra la implementación del enfoque anterior:
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 approach def 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 ans if __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 approach
using 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>
Producción
18
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)