Dada una array arr[] de tamaño N y un entero X, la tarea es encontrar la longitud de la subsecuencia más larga tal que la suma del prefijo en cada elemento de la subsecuencia permanezca mayor que cero.
Ejemplo:
Entrada: arr[] = {-2, -1, 1, 2, -2}, N = 5
Salida: 3
Explicación: La secuencia puede estar formada por elementos en los índices 2, 3 y 4. El prefijo suma en cada elemento permanece mayor que cero: 1, 3, 1Entrada: arr[] = {-2, 3, 3, -7, -5, 1}, N = 6
Salida: 12
Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . La idea es crear una cola de prioridad de montón mínimo y recorrer la array de izquierda a derecha. Agregue el elemento actual arr[i] a sum y minheap, y si la suma se vuelve menor que cero, elimine el elemento más negativo del minheap y réstelo de sum . Se puede seguir el siguiente enfoque para resolver el problema:
- Inicializar un montón mínimo con estructura de datos de cola de prioridad
- Inicialice una suma variable para calcular la suma del prefijo de la subsecuencia deseada
- Itere la array y en cada elemento arr[i] y agregue el valor a la suma y al montón mínimo
- Si el valor de la suma se vuelve menor que cero, elimine el elemento más negativo del montón mínimo y reste ese valor de la suma
- Devuelve el tamaño del montón mínimo como la longitud de la subsecuencia más larga
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate longest length
// of subsequence such that its prefix sum
// at every element stays greater than zero
int maxScore(int arr[], int N)
{
// Variable to store the answer
int score = 0;
// Min heap implementation
// using a priority queue
priority_queue<int, vector<int>,
greater<int> >
pq;
// Variable to store the sum
int sum = 0;
for (int i = 0; i < N; i++) {
// Add the current element
// to the sum
sum += arr[i];
// Push the element in
// the min-heap
pq.push(arr[i]);
// If the sum becomes less than
// zero pop the top element of
// the min-heap and subtract it
// from the sum
if (sum < 0) {
int a = pq.top();
sum -= a;
pq.pop();
}
}
// Return the answer
return pq.size();
}
// Driver Code
int main()
{
int arr[] = { -2, 3, 3, -7, -5, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxScore(arr, N);
return 0;
}
Java
// Java code for the above approach
import java.io.*;
import java.util.PriorityQueue;
class GFG
{
// Function to calculate longest length
// of subsequence such that its prefix sum
// at every element stays greater than zero
static int maxScore(int arr[], int N)
{
// Variable to store the answer
int score = 0;
// Min heap implementation
// using a priority queue
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>();
// Variable to store the sum
int sum = 0;
for (int i = 0; i < N; i++) {
// Add the current element
// to the sum
sum += arr[i];
// Push the element in
// the min-heap
pq.add(arr[i]);
// If the sum becomes less than
// zero pop the top element of
// the min-heap and subtract it
// from the sum
if (sum < 0) {
int a = pq.poll();
sum -= a;
}
}
// Return the answer
return pq.size();
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { -2, 3, 3, -7, -5, 1 };
int N = arr.length;
System.out.println(maxScore(arr, N));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python implementation for the above approach from queue import PriorityQueue # Function to calculate longest length # of subsequence such that its prefix sum # at every element stays greater than zero def maxScore(arr, N): # Variable to store the answer score = 0; # Min heap implementation # using a priority queue pq = PriorityQueue(); # Variable to store the sum sum = 0; for i in range(N) : # Add the current element # to the sum sum += arr[i]; # Push the element in # the min-heap pq.put(arr[i]); # If the sum becomes less than # zero pop the top element of # the min-heap and subtract it # from the sum if (sum < 0): a = pq.queue[0] sum -= a; pq.get() # Return the answer return pq.qsize(); # Driver Code arr = [ -2, 3, 3, -7, -5, 1 ]; N = len(arr) print(maxScore(arr, N)) # This code is contributed by saurabh_jaiswal.
C#
// C# code for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to calculate longest length
// of subsequence such that its prefix sum
// at every element stays greater than zero
static int maxScore(int []arr, int N) {
// Variable to store the answer
int score = 0;
// Min heap implementation
// using a priority queue
List<int> pq = new List<int>();
// Variable to store the sum
int sum = 0;
for (int i = 0; i < N; i++) {
// Add the current element
// to the sum
sum += arr[i];
// Push the element in
// the min-heap
pq.Add(arr[i]);
pq.Sort();
// If the sum becomes less than
// zero pop the top element of
// the min-heap and subtract it
// from the sum
if (sum < 0) {
int a = pq[0];
pq.RemoveAt(0);
sum -= a;
}
}
// Return the answer
return pq.Count;
}
// Driver Code
public static void Main(String[] args) {
int []arr = { -2, 3, 3, -7, -5, 1 };
int N = arr.Length;
Console.WriteLine(maxScore(arr, N));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// javascript code for the above approach
// Function to calculate longest length
// of subsequence such that its prefix sum
// at every element stays greater than zero
function maxScore(arr , N) {
// Variable to store the answer
var score = 0;
// Min heap implementation
// using a priority queue
var pq = [];
// Variable to store the sum
var sum = 0;
for (i = 0; i < N; i++) {
// Add the current element
// to the sum
sum += arr[i];
// Push the element in
// the min-heap
pq.push(arr[i]);
// If the sum becomes less than
// zero pop the top element of
// the min-heap and subtract it
// from the sum
if (sum < 0) {
var a = pq.pop();
sum -= a;
}
}
// Return the answer
return pq.length;
}
// Driver Code
var arr = [ -2, 3, 3, -7, -5, 1 ];
var N = arr.length;
document.write(maxScore(arr, N));
// This code is contributed by Rajput-Ji
</script>
Producción
4
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)