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++
// 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; }
Python3
# 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)
Publicación traducida automáticamente
Artículo escrito por shreyanshgupta838 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA