El subarreglo más largo de celdas no vacías después de eliminar como máximo una sola celda vacía

Dada una array binaria arr[] , la tarea es encontrar el subarreglo más largo de celdas no vacías después de eliminar como máximo 1 celda vacía.
 

Los índices de array llenos con 0 se conocen como celdas vacías, mientras que los índices llenos con 1 se conocen como celdas no vacías .

Ejemplos: 
 

Entrada: arr[] = {1, 1, 0, 1} 
Salida:
Explicación: 
La eliminación de 0 modifica el arreglo a {1, 1, 1}, maximizando así la longitud del subarreglo a 3.
Entrada: arr[] = {1, 1, 1, 1, 1} 
Salida:
 

Enfoque: 
La idea es almacenar las frecuencias de 1 en los prefijos y sufijos de cada índice para calcular secuencias consecutivas más largas de 1 en ambas direcciones de un índice en particular. Siga los pasos a continuación para resolver el problema: 
 

  • Inicialice dos arrays l[] y r[] que almacenan la longitud de los 1 consecutivos más largos en la array arr[] desde el lado izquierdo y derecho de la array respectivamente.
  • Itere sobre la array de entrada sobre los índices (0, N) y aumente la cuenta en 1 para cada arr[i] = 1 . De lo contrario, almacene el valor de la cuenta hasta el índice (i – 1) en l [i], restablezca la cuenta a cero. 
     
  • Del mismo modo, repita los pasos anteriores recorriendo los índices [N – 1, 0] almacene el conteo desde la derecha en r[] .
  • Para cada i -ésimo índice que contiene 0 , calcule la longitud del subarreglo no vacío posible mediante la eliminación de ese 0 , que es igual a l[i] + r[i] .
  • Calcule el máximo de todas esas longitudes e imprima el 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 maximum length 
// of a subarray of 1s after removing 
// at most one 0 
int longestSubarray(int a[], int n) 
{ 
    // Stores the count of consecutive 
    // 1's from left 
    int l[n]; 
  
    // Stores the count of consecutive 
    // 1's from right 
    int r[n]; 
  
    // Traverse left to right 
    for (int i = 0, count = 0; 
        i < n; i++) { 
  
        // If cell is non-empty 
        if (a[i] == 1) 
  
            // Increase count 
            count++; 
  
        // If cell is empty 
        else { 
  
            // Store the count of 
            // consecutive 1's 
            // till (i - 1)-th index 
            l[i] = count; 
            count = 0; 
        } 
    } 
  
    // Traverse from right to left 
    for (int i = n - 1, count = 0; 
        i >= 0; i--) { 
  
        if (a[i] == 1) 
            count++; 
  
        else { 
  
            // Store the count of 
            // consecutive 1s 
            // till (i + 1)-th index 
            r[i] = count; 
            count = 0; 
        } 
    } 
  
    // Stores the length of 
    // longest subarray 
    int ans = -1; 
    for (int i = 0; i < n; ++i) { 
  
        if (a[i] == 0) 
  
            // Store the maximum 
            ans = max(ans, l[i] + r[i]); 
    } 
  
    // If array a contains only 1s 
    // return n else return ans 
    return ans < 0 ? n : ans; 
} 
  
// Driver Code 
int main() 
{ 
    int arr[] = { 0, 1, 1, 1, 0, 1, 
                0, 1, 1 }; 
  
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    cout << longestSubarray(arr, n); 
  
    return 0; 
} 

Java

// Java program for the above approach 
class GFG{ 
      
// Function to find the maximum length 
// of a subarray of 1s after removing 
// at most one 0 
public static int longestSubarray(int[] a, 
                                int n) 
{ 
      
    // Stores the count of consecutive 
    // 1's from left 
    int[] l = new int[n]; 
      
    // Stores the count of consecutive 
    // 1's from right 
    int[] r = new int[n]; 
      
    // Traverse left to right 
    for(int i = 0, count = 0; 
            i < n; i++) 
    { 
          
    // If cell is non-empty 
    if (a[i] == 1) 
          
        // Increase count 
        count++; 
          
    // If cell is empty 
    else
    { 
              
        // Store the count of 
        // consecutive 1's 
        // till (i - 1)-th index 
        l[i] = count; 
        count = 0; 
    } 
    } 
      
    // Traverse from right to left 
    for(int i = n - 1, count = 0; 
            i >= 0; i--) 
    { 
    if (a[i] == 1) 
        count++; 
          
    else
    { 
              
        // Store the count of 
        // consecutive 1s 
        // till (i + 1)-th index 
        r[i] = count; 
        count = 0; 
        } 
    } 
      
    // Stores the length of 
    // longest subarray 
    int ans = -1; 
    for(int i = 0; i < n; ++i) 
    { 
    if (a[i] == 0) 
              
        // Store the maximum 
        ans = Math.max(ans, l[i] + r[i]); 
    } 
      
    // If array a contains only 1s 
    // return n else return ans 
    return ans < 0 ? n : ans; 
} 
  
// Driver code 
public static void main(String[] args) 
{ 
    int[] arr = { 0, 1, 1, 1, 0, 
                1, 0, 1, 1 }; 
    int n = arr.length; 
      
    System.out.println(longestSubarray(arr, n)); 
} 
} 
  
// This code is contributed by divyeshrabadiya07 

Python3

# Python3 program for the above approach 
  
# Function to find the maximum length 
# of a subarray of 1s after removing 
# at most one 0 
def longestSubarray(a, n):
  
    # Stores the count of consecutive 
    # 1's from left 
    l = [0] * (n) 
  
    # Stores the count of consecutive 
    # 1's from right 
    r = [0] * (n)
      
    count = 0
      
    # Traverse left to right 
    for i in range(n):
          
        # If cell is non-empty 
        if (a[i] == 1):
              
            # Increase count 
            count += 1
          
        # If cell is empty 
        else:
              
            # Store the count of 
            # consecutive 1's 
            # till (i - 1)-th index 
            l[i] = count 
            count = 0
      
    count = 0
    # Traverse from right to left
    for i in range(n - 1, -1, -1):
        if (a[i] == 1):
            count += 1
              
        else:
              
            # Store the count of 
            # consecutive 1s 
            # till (i + 1)-th index 
            r[i] = count
            count = 0
      
    # Stores the length of 
    # longest subarray 
    ans = -1
    for i in range(n):
        if (a[i] == 0):
              
            # Store the maximum 
            ans = max(ans, l[i] + r[i])
      
    # If array a contains only 1s 
    # return n else return ans 
    return ans < 0 and n or ans
  
# Driver code 
arr = [ 0, 1, 1, 1, 0, 1, 0, 1, 1 ] 
  
n = len(arr)
  
print(longestSubarray(arr, n))
  
# This code is contributed by sanjoy_62

C#

// C# program for the above approach 
using System;
  
class GFG{ 
      
// Function to find the maximum length 
// of a subarray of 1s after removing 
// at most one 0 
public static int longestSubarray(int[] a,
                                  int n) 
{ 
      
    // Stores the count of consecutive 
    // 1's from left
    int[] l = new int[n]; 
      
    // Stores the count of consecutive 
    // 1's from right 
    int[] r = new int[n]; 
      
    // Traverse left to right 
    for(int i = 0, count = 0; i < n; i++)
    { 
          
        // If cell is non-empty 
        if (a[i] == 1) 
              
            // Increase count 
            count++; 
              
        // If cell is empty 
        else
        { 
              
            // Store the count of 
            // consecutive 1's 
            // till (i - 1)-th index 
            l[i] = count; 
            count = 0; 
        } 
    } 
      
    // Traverse from right to left 
    for(int i = n - 1, count = 0; 
            i >= 0; i--)
    { 
    if (a[i] == 1)
        count++; 
          
    else
    { 
              
        // Store the count of 
        // consecutive 1s 
        // till (i + 1)-th index 
        r[i] = count; 
        count = 0; 
        } 
    } 
      
    // Stores the length of 
    // longest subarray 
    int ans = -1; 
    for(int i = 0; i < n; ++i)
    { 
        if (a[i] == 0) 
                  
            // Store the maximum 
            ans = Math.Max(ans, l[i] + r[i]); 
    } 
      
    // If array a contains only 1s 
    // return n else return ans 
    return ans < 0 ? n : ans; 
}
  
  
// Driver code
public static void Main()
{
    int[] arr = { 0, 1, 1, 1, 0,
                  1, 0, 1, 1 }; 
    int n = arr.Length; 
  
    Console.Write(longestSubarray(arr, n));
}
}
  
// This code is contributed by sanjoy_62

Javascript

<script>
// javascript program for the above approach     
// Function to find the maximum length
    // of a subarray of 1s after removing
    // at most one 0
    function longestSubarray(a , n)
    {
  
        // Stores the count of consecutive
        // 1's from left
        var l = Array(n).fill(0);
  
        // Stores the count of consecutive
        // 1's from right
        var r = Array(n).fill(0);
  
        // Traverse left to right
        for (i = 0, count = 0; i < n; i++) 
        {
  
            // If cell is non-empty
            if (a[i] == 1)
  
                // Increase count
                count++;
  
            // If cell is empty
            else {
  
                // Store the count of
                // consecutive 1's
                // till (i - 1)-th index
                l[i] = count;
                count = 0;
            }
        }
  
        // Traverse from right to left
        for (i = n - 1, count = 0; i >= 0; i--) {
            if (a[i] == 1)
                count++;
  
            else {
  
                // Store the count of
                // consecutive 1s
                // till (i + 1)-th index
                r[i] = count;
                count = 0;
            }
        }
  
        // Stores the length of
        // longest subarray
        var ans = -1;
        for (i = 0; i < n; ++i) {
            if (a[i] == 0)
  
                // Store the maximum
                ans = Math.max(ans, l[i] + r[i]);
        }
  
        // If array a contains only 1s
        // return n else return ans
        return ans < 0 ? n : ans;
    }
  
    // Driver code
        var arr = [ 0, 1, 1, 1, 0, 1, 0, 1, 1 ];
        var n = arr.length;
        document.write(longestSubarray(arr, n));
  
// This code is contributed by Rajput-Ji 
</script>
Producción: 

4

 

Complejidad de tiempo: O (N) donde n es el número de elementos en una array dada. Como estamos usando un bucle para atravesar N veces, nos costará O (N) tiempo 
Espacio auxiliar: O (N), ya que estamos usando espacio adicional.

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array

Publicación traducida automáticamente

Artículo escrito por sayantanpal1 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 *