Dado un arreglo binario arr[] que consta de N elementos, la tarea es encontrar la longitud máxima posible de un subarreglo de solo 1 , después de eliminar un solo par de elementos consecutivos del arreglo. Si no existe tal subarreglo, imprima -1 .
Ejemplos:
Entrada: arr[] = {1, 1, 1, 0, 0, 1}
Salida: 4
Explicación:
La eliminación del par {0, 0} modifica la array a {1, 1, 1, 1}, maximizando así la longitud del subarreglo más largo posible que consta solo de 1.Entrada: arr[] = {1, 1, 1, 0, 0, 0, 1}
Salida: 3
Explicación:
La eliminación de cualquier par consecutivo del subarreglo {0, 0, 0, 1} mantiene el subarreglo más largo posible de 1 , es decir, {1, 1, 1}.
Enfoque ingenuo:
el enfoque más simple para resolver el problema es generar todos los pares posibles de elementos consecutivos de la array y, para cada par, calcular la longitud máxima posible de un subarreglo de 1 ‘s. Finalmente, imprima la longitud máxima posible de dicho subarreglo obtenido.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente:
siga los pasos que se indican a continuación para resolver el problema:
- Inicialice un vector 2D auxiliar V .
- Mantenga un registro de todos los subarreglos contiguos que consisten en solo 1 .
- Almacene la longitud , el índice inicial y el índice final de los subarreglos.
- Ahora, calcule el número de 0 entre dos subarreglos de 1 .
- Según el recuento de 0 obtenido, actualice la longitud máxima de subarreglos posibles:
- Si hay exactamente dos 0 entre dos subarreglos, actualice la longitud máxima posible comparando la longitud combinada de ambos subarreglos.
- Si hay exactamente un 0 entre dos subarreglos, actualice la longitud máxima posible comparando la longitud combinada de ambos subarreglos: 1.
- Finalmente, imprima la longitud máxima posible obtenida
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// subarray length of ones
int maxLen(int A[], int N)
{
// Stores the length, starting
// index and ending index of the
// subarrays
vector<vector<int> > v;
for (int i = 0; i < N; i++) {
if (A[i] == 1) {
// S : starting index
// of the sub-array
int s = i, len;
// Traverse only continuous 1s
while (A[i] == 1 && i < N) {
i++;
}
// Calculate length of the
// sub-array
len = i - s;
// v[i][0] : Length of subarray
// v[i][1] : Starting Index of subarray
// v[i][2] : Ending Index of subarray
v.push_back({ len, s, i - 1 });
}
}
// If no such sub-array exists
if (v.size() == 0) {
return -1;
}
int ans = 0;
// Traversing through the subarrays
for (int i = 0; i < v.size() - 1; i++) {
// Update maximum length
ans = max(ans, v[i][0]);
// v[i+1][1] : Starting index of
// the next Sub-Array
// v[i][2] : Ending Index of the
// current Sub-Array
// v[i+1][1] - v[i][2] - 1 : Count of
// zeros between the two sub-arrays
if (v[i + 1][1] - v[i][2] - 1 == 2) {
// Update length of both subarrays
// to the maximum
ans = max(ans, v[i][0] + v[i + 1][0]);
}
if (v[i + 1][1] - v[i][2] - 1 == 1) {
// Update length of both subarrays - 1
// to the maximum
ans = max(ans, v[i][0] + v[i + 1][0] - 1);
}
}
// Check if the last subarray has
// the maximum length
ans = max(v[v.size() - 1][0], ans);
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 0, 1, 0, 0, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxLen(arr, N) << endl;
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the maximum
// subarray length of ones
static int maxLen(int A[], int N)
{
// Stores the length, starting
// index and ending index of the
// subarrays
List<List<Integer> > v = new ArrayList<>();
for (int i = 0; i < N; i++) {
if (A[i] == 1) {
// S : starting index
// of the sub-array
int s = i, len;
// Traverse only continuous 1s
while (i < N && A[i] == 1) {
i++;
}
// Calculate length of the
// sub-array
len = i - s;
// v[i][0] : Length of subarray
// v[i][1] : Starting Index of subarray
// v[i][2] : Ending Index of subarray
v.add(Arrays.asList(len, s, i - 1));
}
}
// If no such sub-array exists
if (v.size() == 0) {
return -1;
}
int ans = 0;
// Traversing through the subarrays
for (int i = 0; i < v.size() - 1; i++) {
// Update maximum length
ans = Math.max(ans, v.get(i).get(0));
// v[i+1][1] : Starting index of
// the next Sub-Array
// v[i][2] : Ending Index of the
// current Sub-Array
// v[i+1][1] - v[i][2] - 1 : Count of
// zeros between the two sub-arrays
if (v.get(i + 1).get(1) - v.get(i).get(2) - 1
== 2) {
// Update length of both subarrays
// to the maximum
ans = Math.max(ans,
v.get(i).get(0)
+ v.get(i + 1).get(0));
}
if (v.get(i + 1).get(1) - v.get(i).get(2) - 1
== 1) {
// Update length of both subarrays - 1
// to the maximum
ans = Math.max(
ans, v.get(i).get(0)
+ v.get(i + 1).get(0) - 1);
}
}
// Check if the last subarray has
// the maximum length
ans = Math.max(v.get(v.size() - 1).get(0), ans);
return ans;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 0, 1, 0, 0, 1 };
int N = arr.length;
System.out.println(maxLen(arr, N));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach # Function to find the maximum # subarray length of ones def maxLen(A, N): # Stores the length, starting # index and ending index of the # subarrays v = [] i = 0 while i < N: if (A[i] == 1): # S : starting index # of the sub-array s = i # Traverse only continuous 1s while (i < N and A[i] == 1): i += 1 # Calculate length of the # sub-array le = i - s # v[i][0] : Length of subarray # v[i][1] : Starting Index of subarray # v[i][2] : Ending Index of subarray v.append([le, s, i - 1]) i += 1 # If no such sub-array exists if (len(v) == 0): return -1 ans = 0 # Traversing through the subarrays for i in range(len(v) - 1): # Update maximum length ans = max(ans, v[i][0]) # v[i+1][1] : Starting index of # the next Sub-Array # v[i][2] : Ending Index of the # current Sub-Array # v[i+1][1] - v[i][2] - 1 : Count of # zeros between the two sub-arrays if (v[i + 1][1] - v[i][2] - 1 == 2): # Update length of both subarrays # to the maximum ans = max(ans, v[i][0] + v[i + 1][0]) if (v[i + 1][1] - v[i][2] - 1 == 1): # Update length of both subarrays - 1 # to the maximum ans = max(ans, v[i][0] + v[i + 1][0] - 1) # Check if the last subarray has # the maximum length ans = max(v[len(v) - 1][0], ans) return ans # Driver Code if __name__ == "__main__": arr = [1, 0, 1, 0, 0, 1] N = len(arr) print(maxLen(arr, N)) # This code is contributed by chitranayal
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the maximum
// subarray length of ones
static int maxLen(int []A, int N)
{
// Stores the length, starting
// index and ending index of the
// subarrays
List<List<int>> v = new List<List<int>>();
for (int i = 0; i < N; i++)
{
if (A[i] == 1)
{
// S : starting index
// of the sub-array
int s = i, len;
// Traverse only continuous 1s
while (i < N && A[i] == 1)
{
i++;
}
// Calculate length of the
// sub-array
len = i - s;
// v[i,0] : Length of subarray
// v[i,1] : Starting Index of subarray
// v[i,2] : Ending Index of subarray
List<int> l = new List<int>{len, s, i - 1};
v.Add(l);
}
}
// If no such sub-array exists
if (v.Count == 0)
{
return -1;
}
int ans = 0;
// Traversing through the subarrays
for (int i = 0; i < v.Count - 1; i++)
{
// Update maximum length
ans = Math.Max(ans, v[i][0]);
// v[i+1,1] : Starting index of
// the next Sub-Array
// v[i,2] : Ending Index of the
// current Sub-Array
// v[i+1,1] - v[i,2] - 1 : Count of
// zeros between the two sub-arrays
if (v[i + 1][1] - v[i][2] - 1
== 2) {
// Update length of both subarrays
// to the maximum
ans = Math.Max(ans,
v[i][0]
+ v[i + 1][0]);
}
if (v[i + 1][1] - v[i][2] - 1
== 1)
{
// Update length of both subarrays - 1
// to the maximum
ans = Math.Max(
ans, v[i][0]
+ v[i + 1][0] - 1);
}
}
// Check if the last subarray has
// the maximum length
ans = Math.Max(v[v.Count - 1][0], ans);
return ans;
}
// Driver Code
public static void Main(String []args)
{
int []arr = { 1, 0, 1, 0, 0, 1 };
int N = arr.Length;
Console.WriteLine(maxLen(arr, N));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the maximum
// subarray length of ones
function maxLen(A, N)
{
// Stores the length, starting
// index and ending index of the
// subarrays
var v = [];
for (var i = 0; i < N; i++) {
if (A[i] == 1) {
// S : starting index
// of the sub-array
var s = i, len;
// Traverse only continuous 1s
while (A[i] == 1 && i < N) {
i++;
}
// Calculate length of the
// sub-array
len = i - s;
// v[i][0] : Length of subarray
// v[i][1] : Starting Index of subarray
// v[i][2] : Ending Index of subarray
v.push([len, s, i - 1]);
}
}
// If no such sub-array exists
if (v.length == 0) {
return -1;
}
var ans = 0;
// Traversing through the subarrays
for (var i = 0; i < v.length - 1; i++) {
// Update maximum length
ans = Math.max(ans, v[i][0]);
// v[i+1][1] : Starting index of
// the next Sub-Array
// v[i][2] : Ending Index of the
// current Sub-Array
// v[i+1][1] - v[i][2] - 1 : Count of
// zeros between the two sub-arrays
if (v[i + 1][1] - v[i][2] - 1 == 2) {
// Update length of both subarrays
// to the maximum
ans = Math.max(ans, v[i][0] + v[i + 1][0]);
}
if (v[i + 1][1] - v[i][2] - 1 == 1) {
// Update length of both subarrays - 1
// to the maximum
ans = Math.max(ans, v[i][0] + v[i + 1][0] - 1);
}
}
// Check if the last subarray has
// the maximum length
ans = Math.max(v[v.length - 1][0], ans);
return ans;
}
// Driver Code
var arr = [1, 0, 1, 0, 0, 1];
var N = arr.length;
document.write( maxLen(arr, N));
</script>
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Método 2:
Arrays de prefijos y sufijos
Cuente el número de 1 entre las ocurrencias de 0. Si encontramos un 0, entonces necesitamos encontrar la longitud máxima de 1 si omitimos esos 2 elementos consecutivos. Podemos usar los conceptos de arreglos de prefijos y sufijos para resolver el problema.
Encuentre la longitud de los 1 consecutivos desde el inicio de la array y almacene el conteo en la array de prefijos. Encuentre la longitud de los 1 consecutivos desde el final de la array y almacene el conteo en la array final.
Atravesamos ambas arrays y encontramos el número máximo. de 1 s.
Algoritmo:
- Cree dos arrays de prefijo y sufijo de longitud n.
- Inicializar prefijo[0]=0,prefijo[1]=0 y sufijo[n-1]=0,sufijo[n-2]=0. Esto nos dice que no hay 1 antes de los primeros 2 elementos y después de los últimos 2 elementos.
- Ejecute el ciclo de 2 a n-1:
- Si arr[i-2]==1
- prefijo[i]=prefijo[i-1]+1
- de lo contrario si arr[i-2]==0:
- prefijo[i]=0
- Si arr[i-2]==1
- Ejecute el ciclo de n-3 a 0:
- Si arr[i+2]==1
- sufijo[i]=sufijo[i+1]+1
- de lo contrario si arr[i-2]==0:
- sufijo[i]=0
- Si arr[i+2]==1
- Inicializar respuesta=INT_MIN
- for i=0 to n-2: //Cuente el número de 1 omitiendo el elemento actual y el siguiente.
- answer=max(respuesta,prefijo[i+1]+sufijo[i]
- imprimir respuesta
Implementación:
C++
// C++ program to find the maximum count of 1s
#include <bits/stdc++.h>
using namespace std;
void maxLengthOf1s(vector<int> arr, int n)
{
vector<int> prefix(n, 0);
for (int i = 2; i < n; i++)
{
// If arr[i-2]==1 then we increment the
// count of occurrences of 1's
if (arr[i - 2]
== 1)
prefix[i] = prefix[i - 1] + 1;
// else we initialise the count with 0
else
prefix[i] = 0;
}
vector<int> suffix(n, 0);
for (int i = n - 3; i >= 0; i--)
{
// If arr[i+2]==1 then we increment the
// count of occurrences of 1's
if (arr[i + 2] == 1)
suffix[i] = suffix[i + 1] + 1;
// else we initialise the count with 0
else
suffix[i] = 0;
}
int ans = 0;
for (int i = 0; i < n - 1; i++)
{
// We get the maximum count by
// skipping the current and the
// next element.
ans = max(ans, prefix[i + 1] + suffix[i]);
}
cout << ans << "\n";
}
// Driver Code
int main()
{
int n = 6;
vector<int> arr = { 1, 1, 1, 0, 1, 1 };
maxLengthOf1s(arr, n);
return 0;
}
Java
// Java program to find the maximum count of 1s
class GFG{
public static void maxLengthOf1s(int arr[], int n)
{
int prefix[] = new int[n];
for(int i = 2; i < n; i++)
{
// If arr[i-2]==1 then we increment
// the count of occurrences of 1's
if (arr[i - 2] == 1)
prefix[i] = prefix[i - 1] + 1;
// Else we initialise the count with 0
else
prefix[i] = 0;
}
int suffix[] = new int[n];
for(int i = n - 3; i >= 0; i--)
{
// If arr[i+2]==1 then we increment
// the count of occurrences of 1's
if (arr[i + 2] == 1)
suffix[i] = suffix[i + 1] + 1;
// Else we initialise the count with 0
else
suffix[i] = 0;
}
int ans = 0;
for(int i = 0; i < n - 1; i++)
{
// We get the maximum count by
// skipping the current and the
// next element.
ans = Math.max(ans, prefix[i + 1] +
suffix[i]);
}
System.out.println(ans);
}
// Driver code
public static void main(String[] args)
{
int n = 6;
int arr[] = { 1, 1, 1, 0, 1, 1 };
maxLengthOf1s(arr, n);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python program to find the maximum count of 1s def maxLengthOf1s(arr, n): prefix = [0 for i in range(n)] for i in range(2, n): # If arr[i-2]==1 then we increment # the count of occurrences of 1's if(arr[i - 2] == 1): prefix[i] = prefix[i - 1] + 1 # Else we initialise the count with 0 else: prefix[i] = 0 suffix = [0 for i in range(n)] for i in range(n - 3, -1, -1): # If arr[i+2]==1 then we increment # the count of occurrences of 1's if(arr[i + 2] == 1): suffix[i] = suffix[i + 1] + 1 # Else we initialise the count with 0 else: suffix[i] = 0 ans = 0 for i in range(n - 1): # We get the maximum count by # skipping the current and the # next element. ans = max(ans, prefix[i + 1] + suffix[i]) print(ans) # Driver code n = 6 arr = [1, 1, 1, 0, 1, 1] maxLengthOf1s(arr, n) # This code is contributed by avanitrachhadiya2155
C#
// C# program to find the maximum count of 1s
using System;
class GFG{
static void maxLengthOf1s(int[] arr, int n)
{
int[] prefix = new int[n];
for(int i = 2; i < n; i++)
{
// If arr[i-2]==1 then we increment
// the count of occurrences of 1's
if (arr[i - 2] == 1)
prefix[i] = prefix[i - 1] + 1;
// Else we initialise the count with 0
else
prefix[i] = 0;
}
int[] suffix = new int[n];
for(int i = n - 3; i >= 0; i--)
{
// If arr[i+2]==1 then we increment
// the count of occurrences of 1's
if (arr[i + 2] == 1)
suffix[i] = suffix[i + 1] + 1;
// Else we initialise the count with 0
else
suffix[i] = 0;
}
int ans = 0;
for(int i = 0; i < n - 1; i++)
{
// We get the maximum count by
// skipping the current and the
// next element.
ans = Math.Max(ans, prefix[i + 1] + suffix[i]);
}
Console.WriteLine(ans);
}
// Driver code
static void Main()
{
int n = 6;
int[] arr = { 1, 1, 1, 0, 1, 1 };
maxLengthOf1s(arr, n);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program to find
// the maximum count of 1s
function maxLengthOf1s(arr, n)
{
let prefix = new Array(n);
prefix.fill(0);
for(let i = 2; i < n; i++)
{
// If arr[i-2]==1 then we increment
// the count of occurrences of 1's
if (arr[i - 2] == 1)
prefix[i] = prefix[i - 1] + 1;
// Else we initialise the count with 0
else
prefix[i] = 0;
}
let suffix = new Array(n);
suffix.fill(0);
for(let i = n - 3; i >= 0; i--)
{
// If arr[i+2]==1 then we increment
// the count of occurrences of 1's
if (arr[i + 2] == 1)
suffix[i] = suffix[i + 1] + 1;
// Else we initialise the count with 0
else
suffix[i] = 0;
}
let ans = 0;
for(let i = 0; i < n - 1; i++)
{
// We get the maximum count by
// skipping the current and the
// next element.
ans = Math.max(ans, prefix[i + 1] + suffix[i]);
}
document.write(ans);
}
let n = 6;
let arr = [ 1, 1, 1, 0, 1, 1 ];
maxLengthOf1s(arr, n);
</script>
Producción
4
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)