Dada una array arr[] que consta de N enteros, la tarea es encontrar la subsecuencia más larga tal que la suma del prefijo en cada posición de la subsecuencia no sea negativa.
Ejemplos:
Entrada: arr[] = {4, -4, 1, -3, 1, -3}
Salida: 5
Explicación:
Considere la subsecuencia como {4, 1, -3, 1, -3}. Ahora, la suma del prefijo de la subsecuencia elegida es {4, 5, 2, 3, 0}. Dado que la suma del prefijo no es negativa en todos los índices posibles. Por lo tanto, esta subsecuencia tiene una longitud máxima de 5.Entrada: arr[] = {1, 3, 5, 7}
Salida: 4
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las subsecuencias posibles de la array dada e imprimir la longitud de esa subsecuencia que tiene una suma de prefijo no negativa en cada posición y tiene la longitud máxima.
Complejidad de Tiempo: O(2 N )
Espacio Auxiliar: O(2 N )
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la programación dinámica porque tiene la propiedad de subproblemas superpuestos y la propiedad de subestructura óptima . Al igual que otros problemas de Programación Dinámica (DP), se puede evitar el recálculo de los mismos subproblemas construyendo una array temporal que almacene los resultados de los subproblemas. Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos dp[][] donde dp[i][j] almacena la suma máxima posible si hay j elementos válidos hasta la posición i e inicializa la array dp[][] con -1 .
- Itere sobre el rango [0, N – 1] usando la variable i y actualice dp[i][0] como 0 .
- Si el valor de arr[0] es al menos 0 , actualice dp[0][1] como arr[0] . De lo contrario, actualícelo como -1 .
- Iterar sobre el rango [1, N – 1] usando la variable i :
- Iterar sobre el rango [1, i + 1] usando la variable j :
- Si se excluye el elemento actual, es decir, si dp[i – 1][j] no es igual a -1 , actualice dp[i][j] como máximo de dp[i][j] y dp[i – 1] [j] .
- Si se incluye el elemento actual, es decir, si dp[i – 1][j – 1] y dp[i – 1][j – 1] + arr[i] son mayores que 0 , entonces actualice el valor de dp[ i][j] como el máximo de dp[i][j] y dp[i – 1][j – 1] + arr[i] .
- Iterar sobre el rango [1, i + 1] usando la variable j :
- Inicialice una variable, digamos, ans como 0 para almacenar la subsecuencia más larga con una suma de prefijos no negativa en cada posición.
- Iterar en el rango [0, N] usando la variable j y si dp[N – 1][j] es mayor que igual a 0 , entonces actualice el valor de ans como j .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
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 length of the
// longest subsequence with non negative
// prefix sum at each position
void longestSubsequence(int* arr, int N)
{
// Stores the maximum sum possible
// if we include j elements till
// the position i
int dp[N][N + 1];
// Initialize dp array with -1
memset(dp, -1, sizeof dp);
// Maximum subsequence sum by
// including no elements till
// position 'i'
for (int i = 0; i < N; ++i) {
dp[i][0] = 0;
}
// Maximum subsequence sum by
// including first element at
// first position
dp[0][1] = (arr[0] >= 0 ? arr[0] : -1);
// Iterate over all the remaining
// positions
for (int i = 1; i < N; ++i) {
for (int j = 1;
j <= (i + 1); ++j) {
// If the current element
// is excluded
if (dp[i - 1][j] != -1) {
dp[i][j] = max(
dp[i][j], dp[i - 1][j]);
}
// If current element is
// included and if total
// sum is positive or not
if (dp[i - 1][j - 1] >= 0
&& dp[i - 1][j - 1]
+ arr[i]
>= 0) {
dp[i][j] = max(
dp[i][j],
dp[i - 1][j - 1]
+ arr[i]);
}
}
}
int ans = 0;
// Select the maximum j by which
// a non negative prefix sum
// subsequence can be obtained
for (int j = 0; j <= N; ++j) {
if (dp[N - 1][j] >= 0) {
ans = j;
}
}
// Print the answer
cout << ans << endl;
}
// Driver Code
int main()
{
int arr[] = { 4, -4, 1, -3, 1, -3 };
int N = sizeof arr / sizeof arr[0];
longestSubsequence(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the length of the
// longest subsequence with non negative
// prefix sum at each position
static void longestSubsequence(int[] arr, int N)
{
// Stores the maximum sum possible
// if we include j elements till
// the position i
int dp[][] = new int[N][N + 1];
// Initialize dp array with -1
for(int i = 0; i < N; ++i)
{
for(int j = 0; j < N + 1; ++j)
{
dp[i][j] = -1;
}
}
// Maximum subsequence sum by
// including no elements till
// position 'i'
for(int i = 0; i < N; ++i)
{
dp[i][0] = 0;
}
// Maximum subsequence sum by
// including first element at
// first position
dp[0][1] = (arr[0] >= 0 ? arr[0] : -1);
// Iterate over all the remaining
// positions
for(int i = 1; i < N; ++i)
{
for(int j = 1; j <= (i + 1); ++j)
{
// If the current element
// is excluded
if (dp[i - 1][j] != -1)
{
dp[i][j] = Math.max(
dp[i][j], dp[i - 1][j]);
}
// If current element is
// included and if total
// sum is positive or not
if (dp[i - 1][j - 1] >= 0 &&
dp[i - 1][j - 1] + arr[i] >= 0)
{
dp[i][j] = Math.max(dp[i][j],
dp[i - 1][j - 1] +
arr[i]);
}
}
}
int ans = 0;
// Select the maximum j by which
// a non negative prefix sum
// subsequence can be obtained
for(int j = 0; j <= N; ++j)
{
if (dp[N - 1][j] >= 0)
{
ans = j;
}
}
// Print the answer
System.out.println(ans);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, -4, 1, -3, 1, -3 };
int N = arr.length;
longestSubsequence(arr, N);
}
}
// This code is contributed by avijitmondal1998
Python3
# Python3 Program for the above approach # Function to find the length of the # longest subsequence with non negative # prefix sum at each position def longestSubsequence(arr, N): # Stores the maximum sum possible # if we include j elements till # the position i # Initialize dp array with -1 dp = [[-1 for i in range(N + 1)] for i in range(N)] # Maximum subsequence sum by # including no elements till # position 'i' for i in range(N): dp[i][0] = 0 # Maximum subsequence sum by # including first element at # first position dp[0][1] = arr[0] if arr[0] >= 0 else -1 # Iterate over all the remaining # positions for i in range(1, N): for j in range(1, i + 2): # If the current element # is excluded if (dp[i - 1][j] != -1): dp[i][j] = max(dp[i][j], dp[i - 1][j]) # If current element is # included and if total # sum is positive or not if (dp[i - 1][j - 1] >= 0 and dp[i - 1][j - 1] + arr[i] >= 0): dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + arr[i]) ans = 0 # Select the maximum j by which # a non negative prefix sum # subsequence can be obtained for j in range(N + 1): if (dp[N - 1][j] >= 0): ans = j # Print the answer print(ans) # Driver Code arr = [4, -4, 1, -3, 1, -3] N = len(arr) longestSubsequence(arr, N) # This code is contributed by _saurabhy_jaiswal
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the length of the
// longest subsequence with non negative
// prefix sum at each position
static void longestSubsequence(int[] arr, int N)
{
// Stores the maximum sum possible
// if we include j elements till
// the position i
int[,] dp = new int[N, N + 1];
// Initialize dp array with -1
for(int i = 0; i < N; ++i)
{
for(int j = 0; j < N + 1; ++j)
{
dp[i, j] = -1;
}
}
// Maximum subsequence sum by
// including no elements till
// position 'i'
for(int i = 0; i < N; ++i)
{
dp[i, 0] = 0;
}
// Maximum subsequence sum by
// including first element at
// first position
dp[0, 1] = (arr[0] >= 0 ? arr[0] : -1);
// Iterate over all the remaining
// positions
for(int i = 1; i < N; ++i)
{
for(int j = 1; j <= (i + 1); ++j)
{
// If the current element
// is excluded
if (dp[i - 1, j] != -1)
{
dp[i, j] = Math.Max(dp[i, j],
dp[i - 1, j]);
}
// If current element is
// included and if total
// sum is positive or not
if (dp[i - 1, j - 1] >= 0 &&
dp[i - 1, j - 1] + arr[i] >= 0)
{
dp[i, j] = Math.Max(dp[i, j],
dp[i - 1, j - 1] +
arr[i]);
}
}
}
int ans = 0;
// Select the maximum j by which
// a non negative prefix sum
// subsequence can be obtained
for(int j = 0; j <= N; ++j)
{
if (dp[N - 1, j] >= 0)
{
ans = j;
}
}
// Print the answer
Console.Write(ans);
}
// Driver code
public static void Main()
{
int[] arr = { 4, -4, 1, -3, 1, -3 };
int N = arr.Length;
longestSubsequence(arr, N);
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript Program for the above approach
// Function to find the length of the
// longest subsequence with non negative
// prefix sum at each position
function longestSubsequence(arr, N)
{
// Stores the maximum sum possible
// if we include j elements till
// the position i
// Initialize dp array with -1
let dp = Array(N).fill().map(() => Array(N + 1).fill(-1));
// Maximum subsequence sum by
// including no elements till
// position 'i'
for (let i = 0; i < N; ++i) {
dp[i][0] = 0;
}
// Maximum subsequence sum by
// including first element at
// first position
dp[0][1] = (arr[0] >= 0 ? arr[0] : -1);
// Iterate over all the remaining
// positions
for (let i = 1; i < N; ++i) {
for (let j = 1;
j <= (i + 1); ++j) {
// If the current element
// is excluded
if (dp[i - 1][j] != -1) {
dp[i][j] = Math.max(
dp[i][j], dp[i - 1][j]);
}
// If current element is
// included and if total
// sum is positive or not
if (dp[i - 1][j - 1] >= 0
&& dp[i - 1][j - 1]
+ arr[i]
>= 0) {
dp[i][j] = Math.max(
dp[i][j],
dp[i - 1][j - 1]
+ arr[i]);
}
}
}
let ans = 0;
// Select the maximum j by which
// a non negative prefix sum
// subsequence can be obtained
for (let j = 0; j <= N; ++j) {
if (dp[N - 1][j] >= 0) {
ans = j;
}
}
// Print the answer
document.write(ans);
}
// Driver Code
let arr = [4, -4, 1, -3, 1, -3];
let N = arr.length;
longestSubsequence(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción:
5
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA