Dada una array arr[] que consta de N enteros, la tarea es encontrar la longitud de la subsecuencia más larga de modo que la suma del prefijo en cada índice de la subsecuencia sea negativa.
Ejemplos:
Entrada: arr[] = {-1, -3, 3, -5, 8, 2}
Salida: 5
Explicación: La subsecuencia más larga que cumple la condición es {-1, -3, 3, -5, 2}.Entrada: arr[] = {2, -5, 2, -1, 5, 1, -9, 10}
Salida: 6
Explicación: La subsecuencia más larga que cumple la condición es {-1, -3, 3, -5, 2 }.
Enfoque: el problema se puede resolver mediante el uso de una cola de prioridad . Siga los pasos a continuación para resolver el problema:
- Inicialice una cola de prioridad, digamos pq , y una variable, digamos S como 0 , para almacenar los elementos de la subsecuencia formada a partir de elementos hasta un índice i y para almacenar la suma de los elementos en la cola de prioridad.
- Iterar sobre el rango [0, N – 1] usando la variable i y realizar los siguientes pasos:
- Incremente S en arr[i] y empuje arr[i] en pq.
- Iterar hasta que S sea mayor que 0 y, en cada iteración, disminuir S por el elemento superior de pq y luego extraer el elemento superior.
- Finalmente, después de completar los pasos anteriores, imprima pq.size() como respuesta.
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;
// Function to find the maximum length
// of a subsequence such that prefix sum
// of any index is negative
int maxLengthSubsequence(int arr[], int N)
{
// Max priority Queue
priority_queue<int> pq;
// Stores the temporary sum of a
// prefix of selected subsequence
int S = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Increment S by arr[i]
S += arr[i];
// Push arr[i] into pq
pq.push(arr[i]);
// Iterate until S
// is greater than 0
while (S > 0) {
// Decrement S by pq.top()
S -= pq.top();
// Pop the top element
pq.pop();
}
}
// Return the maxLength
return pq.size();
}
// Driver Code
int main()
{
// Given Input
int arr[6] = { -1, -3, 3, -5, 8, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << maxLengthSubsequence(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.Collections;
import java.util.PriorityQueue;
public class GFG
{
// Function to find the maximum length
// of a subsequence such that prefix sum
// of any index is negative
static int maxLengthSubsequence(int arr[], int N)
{
// Max priority Queue
PriorityQueue<Integer> pq = new PriorityQueue<>(
Collections.reverseOrder());
// Stores the temporary sum of a
// prefix of selected subsequence
int S = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Increment S by arr[i]
S += arr[i];
// Add arr[i] into pq
pq.add(arr[i]);
// Iterate until S
// is greater than 0
while (S > 0)
{
// Decrement S by pq.peek()
S -= pq.peek();
// Remove the top element
pq.remove();
}
}
// Return the maxLength
return pq.size();
}
// Driver code
public static void main(String[] args)
{
int arr[] = { -1, -3, 3, -5, 8, 2 };
int N = arr.length;
// Function call
System.out.println(maxLengthSubsequence(arr, N));
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Function to find the maximum length # of a subsequence such that prefix sum # of any index is negative def maxLengthSubsequence(arr, N): # Max priority Queue pq = [] # Stores the temporary sum of a # prefix of selected subsequence S = 0 # Traverse the array arr[] for i in range(N): # Increment S by arr[i] S += arr[i] # Push arr[i] into pq pq.append(arr[i]) # Iterate until S # is greater than 0 pq.sort(reverse = False) while (S > 0): # Decrement S by pq.top() # pq.sort(reverse=False) S = S - max(pq) # Pop the top element pq = pq[1:] # print(len(pq)) # Return the maxLength return len(pq) # Driver Code if __name__ == '__main__': # Given Input arr = [ -1, -3, 3, -5, 8, 2 ] N = len(arr) # Function call print(maxLengthSubsequence(arr, N)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum length
// of a subsequence such that prefix sum
// of any index is negative
static int maxLengthSubsequence(int []arr, int N)
{
// Max priority Queue
List<int> pq = new List<int>();
// Stores the temporary sum of a
// prefix of selected subsequence
int S = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Increment S by arr[i]
S += arr[i];
// Push arr[i] into pq
pq.Add(arr[i]);
pq.Sort();
// Iterate until S
// is greater than 0
while (S > 0) {
pq.Sort();
// Decrement S by pq.top()
S -= pq[pq.Count-1];
// Pop the top element
pq.RemoveAt(0);
}
}
// Return the maxLength
return pq.Count;
}
// Driver Code
public static void Main()
{
// Given Input
int []arr = { -1, -3, 3, -5, 8, 2 };
int N = arr.Length;
// Function call
Console.Write(maxLengthSubsequence(arr, N));
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum length
// of a subsequence such that prefix sum
// of any index is negative
function maxLengthSubsequence(arr, N) {
// Max priority Queue
let pq = new Array();
// Stores the temporary sum of a
// prefix of selected subsequence
let S = 0;
// Traverse the array arr[]
for (let i = 0; i < N; i++) {
// Increment S by arr[i]
S += arr[i];
// Push arr[i] into pq
pq.push(arr[i]);
pq.sort((a, b) => a - b);
// Iterate until S
// is greater than 0
while (S > 0) {
pq.sort((a, b) => a - b);
// Decrement S by pq.top()
S -= pq[pq.length - 1];
// Pop the top element
pq.shift();
}
}
// Return the maxLength
return pq.length;
}
// Driver Code
// Given Input
let arr = [-1, -3, 3, -5, 8, 2];
let N = arr.length;
// Function call
document.write(maxLengthSubsequence(arr, N));
// This code is contributed by gfgking
</script>
Producción:
5
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por parthagarwal1962000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA