Subconjunto de suma máxima que tiene el mismo número de elementos positivos y negativos

Dada una array arr[] , la tarea es encontrar el subconjunto de suma máxima que contiene el mismo número de elementos positivos y negativos.

Ejemplos:

Entrada: arr[] = {1, -2, 3, 4, -5, 8} 
Salida: 6 
Explicación: 
Subconjunto de suma máxima con igual número de elementos positivos y negativos {8, -2}

Entrada: arr[] = {-1, -2, -3, -4, -5} 
Salida: 0 
Explicación: 
Como no hay ningún elemento positivo en la array, el subconjunto de suma máxima será {}

Enfoque: la idea es almacenar elementos negativos y positivos en dos arrays diferentes y luego clasificarlos individualmente en orden creciente. Luego use dos punteros comenzando desde el elemento más alto de cada array e incluya aquellos pares cuya suma sea mayor que 0. De lo contrario, si la suma del par es menor que 0, deje de buscar más elementos porque no habrá tal par posible con un suma mayor que 0 en los pares de la izquierda.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation to find the
// maximum sum subset having equal
// number of positive and negative
// elements in the subset
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find maximum sum
// subset with equal number of
// positive and negative elements
int findMaxSum(int* arr, int n)
{
    vector<int> a;
    vector<int> b;
     
    // Loop to store the positive
    // and negative elements in
    // two different array
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) {
            a.push_back(arr[i]);
        }
        else if (arr[i] < 0) {
            b.push_back(arr[i]);
        }
    }
     
    // Sort both the array
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
     
    // Pointers starting from
    // the highest elements
    int p = a.size() - 1;
    int q = b.size() - 1;
    int s = 0;
     
    // Find pairs having sum
    // greater than zero
    while (p >= 0 && q >= 0) {
        if (a[p] + b[q] > 0) {
            s = s + a[p] + b[q];
        }
        else {
            break;
        }
        p = p - 1;
        q = q - 1;
    }
    return s;
}
 
// Driver code
int main()
{
    int arr1[] = { 1, -2, 3, 4, -5, 8 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
 
    cout << findMaxSum(arr1, n1) << endl;
    return 0;
}

// Java implementation to find the
// maximum sum subset having equal
// number of positive and negative
// elements in the subset
import java.util.*;
 
class GFG{
 
// Function to find maximum sum
// subset with equal number of
// positive and negative elements
static int findMaxSum(int []arr, int n)
{
    Vector<Integer> a = new Vector<Integer>();
    Vector<Integer> b = new Vector<Integer>();
     
    // Loop to store the positive
    // and negative elements in
    // two different array
    for(int i = 0; i < n; i++)
    {
       if (arr[i] > 0)
       {
           a.add(arr[i]);
       }
       else if (arr[i] < 0)
       {
           b.add(arr[i]);
       }
    }
     
    // Sort both the array
    Collections.sort(a);
    Collections.sort(b);
     
    // Pointers starting from
    // the highest elements
    int p = a.size() - 1;
    int q = b.size() - 1;
    int s = 0;
     
    // Find pairs having sum
    // greater than zero
    while (p >= 0 && q >= 0)
    {
        if (a.get(p) + b.get(q) > 0)
        {
            s = s + a.get(p) + b.get(q);
        }
        else
        {
            break;
        }
        p = p - 1;
        q = q - 1;
    }
     
    return s;
}
 
 
// Driver code
public static void main(String[] args)
{
    int arr1[] = { 1, -2, 3, 4, -5, 8 };
    int n1 = arr1.length;
 
    System.out.print(
           findMaxSum(arr1, n1) + "\n");
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation to find the
# maximum sum subset having equal
# number of positive and negative
# elements in the subset
 
# Function to find maximum sum
# subset with equal number of
# positive and negative elements
def findMaxSum(arr, n):
     
    a = []
    b = []
     
    # Loop to store the positive
    # and negative elements in
    # two different array
    for i in range(n):
        if (arr[i] > 0):
            a.append(arr[i])
             
        elif (arr[i] < 0):
            b.append(arr[i])
         
    # Sort both the array
    a.sort()
    b.sort()
     
    # Pointers starting from
    # the highest elements
    p = len(a) - 1
    q = len(b) - 1
    s = 0
     
    # Find pairs having sum
    # greater than zero
    while (p >= 0 and q >= 0):
        if (a[p] + b[q] > 0):
            s = s + a[p] + b[q]
             
        else:
            break
        p = p - 1
        q = q - 1
         
    return s
     
# Driver code
arr1 = [ 1, -2, 3, 4, -5, 8 ]
n1 = len(arr1)
 
print(findMaxSum(arr1, n1))
 
# This code is contributed by shubhamsingh10

// C# implementation to find the
// maximum sum subset having equal
// number of positive and negative
// elements in the subset
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find maximum sum
// subset with equal number of
// positive and negative elements
static int findMaxSum(int []arr, int n)
{
     
    List<int> a = new List<int>();
    List<int> b = new List<int>();
     
    // Loop to store the positive
    // and negative elements in
    // two different array
    for(int i = 0; i < n; i++)
    {
        if (arr[i] > 0)
        {
            a.Add(arr[i]);
        }
        else if (arr[i] < 0)
        {
            b.Add(arr[i]);
        }
    }
     
    // Sort both the array
    a.Sort();
    b.Sort();
     
    // Pointers starting from
    // the highest elements
    int p = a.Count - 1;
    int q = b.Count - 1;
    int s = 0;
     
    // Find pairs having sum
    // greater than zero
    while (p >= 0 && q >= 0)
    {
        if (a[p] + b[q] > 0)
        {
            s = s + a[p] + b[q];
        }
        else
        {
            break;
        }
         
        p = p - 1;
        q = q - 1;
    }
    return s;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr1 = { 1, -2, 3, 4, -5, 8 };
    int n1 = arr1.Length;
 
    Console.Write(findMaxSum(arr1, n1) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascript implementation to find the
// maximum sum subset having equal
// number of positive and negative
// elements in the subset
 
// Function to find maximum sum
// subset with equal number of
// positive and negative elements
function findMaxSum(arr, n)
{
    var a = [];
    var b = [];
     
    // Loop to store the positive
    // and negative elements in
    // two different array
    for(var i = 0; i < n; i++)
    {
        if (arr[i] > 0)
        {
            a.push(arr[i]);
        }
        else if (arr[i] < 0)
        {
            b.push(arr[i]);
        }
    }
     
    // Sort both the array
    a.sort((a, b) => a - b)
    b.sort((a, b) => a - b)
     
    // Pointers starting from
    // the highest elements
    var p = a.length - 1;
    var q = b.length - 1;
    var s = 0;
     
    // Find pairs having sum
    // greater than zero
    while (p >= 0 && q >= 0)
    {
        if (a[p] + b[q] > 0)
        {
            s = s + a[p] + b[q];
        }
        else
        {
            break;
        }
        p = p - 1;
        q = q - 1;
    }
    return s;
}
 
// Driver code
var arr1 = [ 1, -2, 3, 4, -5, 8 ];
var n1 = arr1.length;
 
document.write( findMaxSum(arr1, n1));
 
// This code is contributed by rrrtnx
 
</script>

6

Análisis de rendimiento:

• Complejidad de tiempo: O(N*logN)
• Espacio Auxiliar: O(N)