El subconjunto más grande de Array que tiene una suma de al menos 0

Dada una array arr[] que contiene N enteros, la tarea es encontrar el subconjunto más grande que tenga una suma de al menos 0.

Ejemplos:

Entrada: arr[] = {5, -7, 0, -5, -3, -1}
Salida: 4
Explicación: El subconjunto más grande que se puede seleccionar es {5, 0, -3, -1}. tiene talla 4

Entrada: arr[] = {1, -4, -2, -3}
Salida: 1

Enfoque ingenuo: la idea básica para resolver el problema es usar recursividad basada en la siguiente idea:

En cada índice, hay dos opciones, seleccionar ese elemento o no. Si la suma se vuelve negativa, no la seleccione, de lo contrario, selecciónela. Y de cada recursión devuelva el tamaño del subconjunto más grande posible entre las dos opciones.

Siga los pasos que se mencionan a continuación:

• Use una función recursiva y para cada índice hay dos opciones, seleccione ese elemento o no.
• Evite seleccionar ese elemento, cuyo valor hace que la suma sea negativa.  
• Devuelve el recuento de elementos seleccionados máximos de ambas opciones.
• El máximo entre todos estos es el tamaño de subconjunto requerido.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return maximum count
int pick_max_elements(int pos, int sum,
                      int n, int arr[])
{
 
    // Return if the end of the array
    // is reached
    if (pos == n)
        return 0;
 
    int taken = INT_MIN;
 
    // If we select element at index pos
    if (sum + arr[pos] >= 0)
        taken = 1
                + pick_max_elements(pos + 1,
                                    sum + arr[pos],
                                    n, arr);
 
    int not_taken
        = pick_max_elements(pos + 1,
                            sum, n, arr);
 
    // Return the maximize steps taken
    return max(taken, not_taken);
}
 
// Driver code
int main()
{
    int arr[] = { 1, -4, -2, -3 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function to pick maximum number
    // of elements
    cout << pick_max_elements(0, 0, N, arr);
    return 0;
}

// Java code to implement the approach
import java.util.*;
class GFG
{
 
  // Function to return maximum count
  public static int pick_max_elements(int pos, int sum,
                                      int n, int arr[])
  {
 
    // Return if the end of the array
    // is reached
    if (pos == n)
      return 0;
 
    int taken = Integer.MIN_VALUE;
 
    // If we select element at index pos
    if (sum + arr[pos] >= 0)
      taken = 1
      + pick_max_elements(
      pos + 1, sum + arr[pos], n, arr);
 
    int not_taken
      = pick_max_elements(pos + 1, sum, n, arr);
 
    // Return the maximize steps taken
    return Math.max(taken, not_taken);
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int arr[] = { 1, -4, -2, -3 };
    int N = arr.length;
 
    // Function to pick maximum number
    // of elements
    System.out.print(pick_max_elements(0, 0, N, arr));
  }
}
 
// This code is contributed by Taranpreet

# Python code to implement the approach
INT_MIN = -(1e9 + 7)
 
# Function to return maximum count
def pick_max_elements(pos, sum, n, arr):
 
    # Return if the end of the array
    # is reached
    if (pos == n):
        return 0
 
    taken = INT_MIN
 
    # If we select element at index pos
    if (sum + arr[pos] >= 0):
        taken = 1 + pick_max_elements(pos + 1, sum + arr[pos], n, arr)
 
    not_taken = pick_max_elements(pos + 1, sum, n, arr)
 
    # Return the maximize steps taken
    return max(taken, not_taken)
 
# Driver code
arr = [1, -4, -2, -3]
N = len(arr)
 
# Function to pick maximum number
# of elements
print(pick_max_elements(0, 0, N, arr))
 
# This code is contributed by Samim Hossain Mondal.

// C# code to implement the approach
using System;
class GFG {
 
  // Function to return maximum count
  public static int pick_max_elements(int pos, int sum,
                                      int n, int[] arr)
  {
 
    // Return if the end of the array
    // is reached
    if (pos == n)
      return 0;
 
    int taken = Int32.MinValue;
 
    // If we select element at index pos
    if (sum + arr[pos] >= 0)
      taken = 1
      + pick_max_elements(
      pos + 1, sum + arr[pos], n, arr);
 
    int not_taken
      = pick_max_elements(pos + 1, sum, n, arr);
 
    // Return the maximize steps taken
    return Math.Max(taken, not_taken);
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    int[] arr = { 1, -4, -2, -3 };
    int N = arr.Length;
 
    // Function to pick maximum number
    // of elements
    Console.Write(pick_max_elements(0, 0, N, arr));
  }
}
 
// This code is contributed by ukasp.

<script>
    // JavaScript code for the above approach
 
    // Function to return maximum count
    function pick_max_elements(pos, sum,
        n, arr) {
 
        // Return if the end of the array
        // is reached
        if (pos == n)
            return 0;
 
        let taken = Number.MIN_VALUE;
 
        // If we select element at index pos
        if (sum + arr[pos] >= 0)
            taken = 1
                + pick_max_elements(pos + 1,
                    sum + arr[pos],
                    n, arr);
 
        let not_taken
            = pick_max_elements(pos + 1,
                sum, n, arr);
 
        // Return the maximize steps taken
        return Math.max(taken, not_taken);
    }
 
    // Driver code
 
    let arr = [1, -4, -2, -3];
    let N = arr.length;
 
    // Function to pick maximum number
    // of elements
    document.write(pick_max_elements(0, 0, N, arr));
 
    // This code is contributed by Potta Lokesh
</script>

1

Complejidad de Tiempo: O( 2 ^N )  
Espacio Auxiliar: O( N )

Enfoque eficiente: el enfoque eficiente utiliza multiset basado en la siguiente idea:

Recorra desde el inicio de la array y si en cualquier índice la suma hasta ahora se vuelve negativa, borre el elemento mínimo hasta el índice actual del subconjunto. Esto aumentará la suma del subconjunto. 
Para encontrar de manera eficiente se utiliza el multiconjunto mínimo.

Siga la ilustración dada a continuación para una mejor comprensión.

Ilustración:

Considere la array arr[] = {1, -4, -2, -3}  

multiconjunto <int> s,

-> Insertar arr[0] en s. s = {1}. suma = suma + arr[0] = 1

-> Insertar arr[1] en s. s = {-4, 1}. sum = sum + arr[1] = -3 
-> Eliminar el elemento más pequeño (es decir, -4). suma = -3 – (-4) = 1.

-> Insertar arr[2] en s. s = {-2, 1}. sum = sum + arr[2] = -1 
-> Eliminar el elemento más pequeño (es decir, -2). suma = -1 – (-2) = 1.

-> Insertar arr[3] en s. s = {-3, 1}. sum = sum + arr[1] = -2 
-> Eliminar el elemento más pequeño (es decir, es -3). suma = -2 – (-3) = 1.

Total 1 elemento en el subconjunto

 Siga los pasos a continuación para resolver este problema: 

• Iterar de i = 0 a N 
  • Incrementa el conteo
  • Agregue el elemento actual a la suma del subconjunto.
  • Inserte arr[i] en el conjunto.
  • Si la suma se vuelve negativa, reste el valor más pequeño del conjunto y también elimine el elemento más pequeño del conjunto.
  • Decrementar el conteo
• Devuelve el conteo final.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return max count
int pick_max_elements(int arr[], int n)
{
    int cnt = 0, sum = 0;
 
    // To store elements in sorted order
    multiset<int> s;
 
    for (int i = 0; i < n; i++) {
        sum += arr[i];
 
        // An element added,
        // so increase the cnt
        cnt++;
        s.insert(arr[i]);
        if (sum < 0) {
            sum = sum - *s.begin();
 
            // To remove the
            // smallest element
            s.erase(s.begin());
 
            // Removed an element,
            // so decrease the cnt
            cnt--;
        }
    }
    return cnt;
}
 
// Driver code
int main()
{
    int arr[] = { 1, -4, -2, -3 };
 
    // Size of array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function to pick
    // maximum number of elements
    cout << pick_max_elements(arr, N);
    return 0;
}

// JAVA code to implement the above approach
import java.util.*;
class GFG {
 
// Function to return max count
static int pick_max_elements(int arr[], int n)
{
    int cnt = 0, sum = 0;
 
    // To store elements in sorted order
    Vector<Integer> s = new Vector<>();
 
    for (int i = 0; i < n; i++) {
        sum += arr[i];
 
        // An element added,
        // so increase the cnt
        cnt++;
        s.add(arr[i]);
        if (sum < 0) {
            sum = sum - s.get(0);
 
            // To remove the
            // smallest element
            s.remove(0);
 
            // Removed an element,
            // so decrease the cnt
            cnt--;
        }
    }
    return cnt;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, -4, -2, -3 };
    int N = arr.length;
 
    // Function to pick maximum number
    // of elements
    System.out.print(pick_max_elements(arr, N));
}
}
 
// This code is contributed by sanjoy_62.

# Python3 code to implement the approach
 
# using bisect.insort() to
# store elements in sorted form
import bisect
 
# Function to return max count
def pick_max_elements(arr, n) :
    cnt = 0
    sum = 0
 
    # To store elements in sorted order
    s = []
 
    for i in range(0,n) :
        sum += arr[i]
 
        # An element added,
        # so increase the cnt
        cnt += 1
        bisect.insort(s, arr[i])
         
        if sum < 0 :
            sum = sum - s[0]
 
            # To remove the
            # smallest element
             
            s.pop(0)
 
            # Removed an element,
            # so decrease the cnt
            cnt -= 1
    return cnt
 
# Driver code
if __name__ == "__main__":
 
    arr = [ 1, -4, -2, -3 ]
    N = len(arr)
     
    # Function to pick maximum number
    # of elements
    print(pick_max_elements(arr, N))
 
# This code is contributed by Pushpesh Raj

1

Complejidad temporal: O( N * log N )
Espacio auxiliar: O(N )