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: 3
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: 5
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