Longitud máxima de segmentos de 0’s y 1’s

Posted on by Rudeus Greyrat

Dada una string compuesta por unos y ceros. La tarea es encontrar la longitud máxima de los segmentos de cuerda de modo que un número de 1 en cada segmento sea mayor que 0.
Nota: Cada segmento tomado debe ser distinto. El índice comienza desde 0.
Ejemplos: 
 

Entrada: str = “100110001010001” 
Salida: 9 
Primer segmento del índice 0 al 4 (10011), longitud total = 5 
Segundo segmento del índice 8 al 10 (101), longitud total = 3 
Tercer segmento del índice 14 al 14 (1) , longitud total = 1, por lo que la
respuesta es 5 + 3 + 1 = 9
Entrada: str = “0010111101100000” 
Salida: 13 
La longitud máxima se puede formar tomando un segmento 
desde el índice 0 hasta el índice 12 (0010111101100), 
es decir, de longitud total = 13

Acercarse: 
 

  1. Si start == n, surge la condición límite, devuelve 0.
  2. Ejecute un bucle desde el inicio hasta n, calculando para cada subarreglo hasta n.
  3. Si el carácter es 1, entonces incremente el conteo de 1; de lo contrario, incremente el conteo de 0.
  4. Si el recuento de 1 es mayor que 0, llame recursivamente a la función para el índice (k+1), es decir, el siguiente índice y agregue la longitud restante, es decir, k-start+1.
  5. De lo contrario, solo llame recursivamente a la función para el siguiente índice k+1.
  6. Devuelve dp[inicio].

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursive Function to find total length of the array
// Where 1 is greater than zero
int find(int start, string adj, int n, int dp[])
{
    // If reaches till end
    if (start == n)
        return 0;
 
    // If dp is saved
    if (dp[start] != -1)
        return dp[start];
 
    dp[start] = 0;
    int one = 0, zero = 0, k;
 
    // Finding for each length
    for (k = start; k < n; k++) {
 
        // If the character scanned is 1
        if (adj[k] == '1')
            one++;
        else
            zero++;
 
        // If one is greater than zero, add total
        // length scanned till now
        if (one > zero)
            dp[start] = max(dp[start], find(k + 1, adj, n, dp)
                                           + k - start + 1);
 
        // Continue with next length
        else
            dp[start] = max(dp[start], find(k + 1, adj, n, dp));
    }
 
    // Return the value for start index
    return dp[start];
}
 
// Driver Code
int main()
{
    string adj = "100110001010001";
 
    // Size of string
    int n = adj.size();
    int dp[n + 1];
    memset(dp, -1, sizeof(dp));
    // Calling the function to find the value of function
 
    cout << find(0, adj, n, dp) << endl;
 
    return 0;
}

Java

// Java implementation of
// above approach
import java.util.*;
import java.lang.Math;
 
class GFG
{
// Recursive Function to find
// total length of the array
// Where 1 is greater than zero
public static int find(int start, String adj,
                       int n, int dp[])
{
         
    // If reaches till end
    if (start == n)
        return 0;
     
    // If dp is saved
    if (dp[start] != -1)
        return dp[start];
     
    dp[start] = 0;
    int one = 0, zero = 0, k;
     
    // Finding for each length
    for (k = start; k < n; k++)
    {
     
        // If the character scanned is 1
        if (adj.charAt(k) == '1')
            one++;
        else
            zero++;
     
        // If one is greater than
        // zero, add total length
        // scanned till now
        if (one > zero)
            dp[start] = Math.max(dp[start],
                            find(k + 1, adj, n, dp) +
                                 k - start + 1);
     
        // Continue with next length
        else
            dp[start] = Math.max(dp[start],
                            find(k + 1, adj, n, dp));
    }
     
    return dp[start];
}
 
// Driver code
public static void main (String[] args)
{
    String adj = "100110001010001";
 
    // Size of string
    int n = adj.length();
    int dp[] = new int[n + 1];
    Arrays.fill(dp, -1);
     
        // Calling the function to find
        // the value of function
        System.out.println(find(0, adj, n, dp));
}
}
 
// This code is contributed
// by Kirti_Mangal

Python3

# Python 3 implementation of above approach
 
# Recursive Function to find total length
# of the array where 1 is greater than zero
def find(start, adj, n, dp):
     
    # If reaches till end
    if (start == n):
        return 0
 
    # If dp is saved
    if (dp[start] != -1):
        return dp[start]
 
    dp[start] = 0
    one = 0
    zero = 0
     
    # Finding for each length
    for k in range(start, n, 1):
         
        # If the character scanned is 1
        if (adj[k] == '1'):
            one += 1
        else:
            zero += 1
 
        # If one is greater than zero, add
        # total length scanned till now
        if (one > zero):
            dp[start] = max(dp[start],
                            find(k + 1, adj, n, dp) +
                                 k - start + 1)
 
        # Continue with next length
        else:
            dp[start] = max(dp[start],
                            find(k + 1, adj, n, dp))
 
    # Return the value for start index
    return dp[start]
 
# Driver Code
if __name__ == '__main__':
    adj = "100110001010001"
 
    # Size of string
    n = len(adj)
    dp = [-1 for i in range(n + 1)]
     
    # Calling the function to find the
    # value of function
    print(find(0, adj, n, dp))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of above approach
using System;
   
class GFG
{
    // Recursive Function to find total length of the array
    // Where 1 is greater than zero
    public static int find(int start, string adj, int n, int[] dp)
    {
        // If reaches till end
        if (start == n)
            return 0;
       
        // If dp is saved
        if (dp[start] != -1)
            return dp[start];
       
        dp[start] = 0;
        int one = 0, zero = 0, k;
       
        // Finding for each length
        for (k = start; k < n; k++) {
       
            // If the character scanned is 1
            if (adj[k] == '1')
                one++;
            else
                zero++;
       
            // If one is greater than zero, add total
            // length scanned till now
            if (one > zero)
                dp[start] = Math.Max(dp[start], find(k + 1, adj, n, dp)
                                               + k - start + 1);
       
            // Continue with next length
            else
                dp[start] = Math.Max(dp[start], find(k + 1, adj, n, dp));
        }
       
        // Return the value for start index
        return dp[start];
    }
       
    // Driver Code
    static void Main()
    {
        string adj = "100110001010001";
   
        // Size of string
        int n = adj.Length;
        int[] dp = new int[n + 1];
        for(int i = 0; i <= n; i++)
            dp[i] = -1;
        // Calling the function to find the value of function
       
        Console.Write(find(0, adj, n, dp) + "\n");
    }
    //This code is contributed by DrRoot_
}

PHP

<?php
// PHP implementation of above approach
 
// Recursive Function to find total length
// of the array where 1 is greater than zero
function find($start, $adj, $n, $dp)
{
     
    // If reaches till end
    if ($start == $n)
        return 0;
 
    // If $dp is saved
    if ($dp[$start] != -1)
        return $dp[$start];
 
    $dp[$start] = 0;
    $one = 0;
    $zero = 0;
 
    // Finding for each length
    for ($k = $start; $k < $n; $k++)
    {
 
        // If the character scanned is 1
        if ($adj[$k] == '1')
            $one++;
        else
            $zero++;
 
        // If one is greater than zero, add total
        // length scanned till now
        if ($one > $zero)
            $dp[$start] = max($dp[$start],
                         find($k + 1, $adj, $n, $dp) +
                              $k - $start + 1);
 
        // Continue with next length
        else
            $dp[$start] = max($dp[$start],
                         find($k + 1, $adj, $n, $dp));
    }
 
    // Return the value for $start index
    return $dp[$start];
}
 
// Driver Code
$adj = "100110001010001";
 
// Size of string
$n = strlen($adj);
$dp = array_fill(0, $n + 1, -1);
 
// Calling the function
// to find the value of function
echo find(0, $adj, $n, $dp);
 
// This code is contributed by ihritik
?>

Javascript

<script>
// javascript implementation of
// above approach
 
    // Recursive Function to find
    // total length of the array
    // Where 1 is greater than zero
    function find(start,  adj , n , dp) {
 
        // If reaches till end
        if (start == n)
            return 0;
 
        // If dp is saved
        if (dp[start] != -1)
            return dp[start];
 
        dp[start] = 0;
        var one = 0, zero = 0, k;
 
        // Finding for each length
        for (k = start; k < n; k++) {
 
            // If the character scanned is 1
            if (adj[k] == '1')
                one++;
            else
                zero++;
 
            // If one is greater than
            // zero, add total length
            // scanned till now
            if (one > zero)
                dp[start] = Math.max(dp[start], find(k + 1, adj, n, dp) + k - start + 1);
 
            // Continue with next length
            else
                dp[start] = Math.max(dp[start], find(k + 1, adj, n, dp));
        }
 
        return dp[start];
    }
 
    // Driver code
        var adj = "100110001010001";
 
        // Size of string
        var n = adj.length;
        var dp = Array(n + 1).fill(-1);
     
 
        // Calling the function to find
        // the value of function
        document.write(find(0, adj, n, dp));
 
// This code is contributed by umadevi9616
</script>
Producción: 

9

 

Publicación traducida automáticamente

Artículo escrito por atulim y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *