Diferencia máxima posible de la suma de dos subconjuntos de una array | conjunto 2

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)

Publicación traducida automáticamente

Artículo escrito por bileyroy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *