La subsecuencia más grande tal que su suma de prefijos nunca se vuelve negativa

Dada una array arr[] que contiene números enteros. La tarea es encontrar la subsecuencia más grande tal que en cualquier momento la suma del prefijo de esa subsecuencia no sea negativa.

Ejemplos:

Entrada: arr[] = {-3, -3, -7, -7, -1, -7, 3, 3, -2, -1, 0, -7}
Salida: 3 3 -2 -1 0
Explicación : Agregar -3 hace que la suma sea negativa, por lo que no se puede incluir. Del mismo modo, -3, -7, -7, -1, -7, -7 no se pueden incluir. Solo se pueden incluir 3, 3, -2, -1, 0.

Entrada: arr[] = {3, 4, -8, 6, -7, 5}
Salida: 3 4 6 -7 5
Explicación: 3, 4 se pueden sumar ya que hacen que la suma sea positiva pero cuando se suma -8 la suma se vuelve negativo por lo que no se puede incluir el resto se pueden incluir todos los números.

Enfoque: este problema se puede resolver utilizando Min Heap . Siga los pasos a continuación para resolver el problema dado. 

• Al principio, inicialice las variables ‘s’=0 y ‘c’=0 , para almacenar la suma de los elementos de la array y el recuento de elementos, respectivamente.
• Tome una cola de prioridad mínima para almacenar los elementos negativos.
• Ahora comience desde el elemento más a la izquierda, tome la suma del elemento actual, empújelo al vector y aumente la cuenta .
• Si el elemento actual es menor que cero, colóquelo en la cola de prioridad mínima .
• Si la suma se vuelve menor que cero, reste el número negativo más grande (o el número más pequeño) de la cola de prioridad de la suma y extraiga ese elemento de la cola de prioridad y también disminuya el conteo del elemento, así como elimine ese elemento del vector .
• Después de recorrer toda la array, obtenemos la subsecuencia deseada en el vector .

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the largest subsequence
// satisfying given conditions
void FindMaxSubsequence(int* a, int n)
{
    // Min priority queue
    priority_queue<int, vector<int>,
                   greater<int> >
        v;
 
    int c = 0, s = 0;
 
    vector<int> v1;
    vector<int>::iterator it;
 
    for (int i = 0; i < n; i++) {
        // Current sum
        s += a[i];
 
        // Push the subsequence
        v1.push_back(a[i]);
 
        // Current count
        c++;
 
        // Storing negative elements
        // in priority queue
        if (a[i] < 0)
            v.push(a[i]);
 
        // If sum is less than zero
        // than subtract largest
        // negative number from left
        // and decrease the count
        if (s < 0) {
            s -= v.top();
            it = find(v1.begin(), v1.end(), v.top());
 
            // Erase the added vector
            v1.erase(it);
            v.pop();
            c--;
        }
    }
 
    // Largest subsequence
    for (auto i : v1) {
        cout << i << " ";
    }
}
 
// Driver Code
int main()
{
 
    int arr[] = { -3, -3, -7, -7, -1, -7,
                  3, 3, -2, -1, 0, -7 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    FindMaxSubsequence(arr, N);
    return 0;
}

# Python code for the above approach
from queue import PriorityQueue
 
# Function to find the largest subsequence
# satisfying given conditions
def FindMaxSubsequence(a, n):
 
    # Min priority queue
    v = PriorityQueue()
 
    c = 0
    s = 0
    v1 = []
 
    for i in range(n):
        # Current sum
        s += a[i]
 
        # Push the subsequence
        v1.append(a[i])
 
        # Current count
        c = c + 1
 
        # Storing negative elements
        # in priority queue
        if a[i] < 0:
            v.put(a[i])
 
        # If sum is less than zero
        # than subtract largest
        # negative number from left
        # and decrease the count
        if (s < 0):
            t = v.get()
            s = s-t
            # Erase the added vector
            v1.remove(t)
 
            c = c - 1
 
    # Largest subsequence
    for i in range(len(v1)):
        print(v1[i], end = " ")
 
# Driver Code
arr = [-3, -3, -7, -7, -1, -7,
       3, 3, -2, -1, 0, -7]
 
N = len(arr)
 
# Function Call
FindMaxSubsequence(arr, N)
 
# This code is contributed by Potta Lokesh

3 3 -2 -1 0 

Complejidad temporal: O(N logN) 
Espacio auxiliar: O(N)