Subsecuencia más larga con suma de prefijo no negativo en cada posición

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] .
• 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++ 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 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 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# 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

<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>

5

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N ² )