Dada una array circular binaria de tamaño N, la tarea es encontrar el número máximo de recuento de 1 consecutivos presentes en la array circular.
Ejemplos:
Entrada: arr[] = {1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1}
Salida: 6
Las últimas 4 y primeras 2 posiciones tienen 6 unos consecutivos.
Entrada: a[] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1}
Salida: 1
Una solución ingenua es crear una array de tamaño 2*N donde N es el tamaño de la array de entrada. Copiamos la array de entrada dos veces en esta array. Ahora necesitamos encontrar los 1 consecutivos más largos en esta array binaria en un recorrido.
Solución eficiente: se pueden seguir los siguientes pasos para resolver el problema anterior:
- En lugar de crear un arreglo de tamaño 2*N para implementar el arreglo circular, podemos usar el operador de módulo para atravesar el arreglo circularmente.
- Iterar de 0 a 2*N y encontrar el número consecutivo de 1 como:
- Recorra la array de izquierda a derecha.
- Cada vez que recorre, calcule el índice actual como (i%N) para recorrer la array circularmente cuando i>N .
- Si vemos un 1, incrementamos la cuenta y la comparamos con el máximo hasta el momento. Si vemos un 0, reiniciamos el conteo como 0.
- Salga del bucle cuando a[i]==0 e i>=n para reducir la complejidad del tiempo en algunos casos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count maximum consecutive
// 1's in a binary circular array
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of maximum
// consecutive 1's in a binary circular array
int getMaxLength(bool arr[], int n)
{
// Starting index
int start = 0;
// To store the maximum length of the
// prefix of the given array with all 1s
int preCnt = 0;
while (start < n && arr[start] == 1) {
preCnt++;
start++;
}
// Ending index
int end = n - 1;
// To store the maximum length of the
// suffix of the given array with all 1s
int suffCnt = 0;
while (end >= 0 && arr[end] == 1) {
suffCnt++;
end--;
}
// The array contains all 1s
if (start > end)
return n;
// Find the maximum length subarray
// with all 1s from the remaining not
// yet traversed subarray
int midCnt = 0;
// To store the result for middle 1s
int result = 0;
for (int i = start; i <= end; i++) {
if (arr[i] == 1) {
midCnt++;
result = max(result, midCnt);
}
else {
midCnt = 0;
}
}
// (preCnt + suffCnt) is the subarray when
// the given array is assumed to be circular
return max(result, preCnt + suffCnt);
}
// Driver code
int main()
{
bool arr[] = { 1, 1, 0, 0, 1, 0, 1,
0, 1, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << getMaxLength(arr, n);
return 0;
}
Java
// Java program to count maximum consecutive
// 1's in a binary circular array
class GfG {
// Function to return the count of maximum
// consecutive 1's in a binary circular array
static int getMaxLength(int arr[], int n)
{
// Starting index
int start = 0;
// To store the maximum length of the
// prefix of the given array with all 1s
int preCnt = 0;
while (start < n && arr[start] == 1) {
preCnt++;
start++;
}
// Ending index
int end = n - 1;
// To store the maximum length of the
// suffix of the given array with all 1s
int suffCnt = 0;
while (end >= 0 && arr[end] == 1) {
suffCnt++;
end--;
}
// The array contains all 1s
if (start > end)
return n;
// Find the maximum length subarray
// with all 1s from the remaining not
// yet traversed subarray
int midCnt = 0;
// To store the result for middle 1s
int result = 0;
for (int i = start; i <= end; i++) {
if (arr[i] == 1) {
midCnt++;
result = Math.max(result, midCnt);
}
else {
midCnt = 0;
}
}
// (preCnt + suffCnt) is the subarray when
// the given array is assumed to be circular
return Math.max(result, preCnt + suffCnt);
}
// Driver code
public static void main(String[] args)
{
int arr[] = new int[] { 1, 1, 0, 0, 1, 0,
1, 0, 1, 1, 1, 1 };
int n = arr.length;
System.out.println(getMaxLength(arr, n));
}
}
// This code is contributed by Prerna Saini
Python3
# Python 3 program to count maximum consecutive # 1's in a binary circular array # Function to return the count of # maximum consecutive 1's in a # binary circular array def getMaxLength(arr, n): # Starting index start = 0 # To store the maximum length of the # prefix of the given array with all 1s preCnt = 0 while(start < n and arr[start] == 1): preCnt = preCnt + 1 start = start + 1 # Ending index end = n - 1 # To store the maximum length of the # suffix of the given array with all 1s suffCnt = 0 while(end >= 0 and arr[end] == 1): suffCnt = suffCnt + 1 end = end - 1 # The array contains all 1s if(start > end): return n # Find the maximum length subarray # with all 1s from the remaining not # yet traversed subarray midCnt = 0 i = start # To store the result for middle 1s result = 0 while(i <= end): if(arr[i] == 1): midCnt = midCnt + 1 result = max(result, midCnt) else: midCnt = 0 i = i + 1 # (preCnt + suffCnt) is the subarray when # the given array is assumed to be circular return max(result, preCnt + suffCnt) # Driver code if __name__ == '__main__': arr = [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1] n = len(arr) print(getMaxLength(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to count maximum consecutive
// 1's in a binary circular array
using System;
class GFG {
// Function to return the count of maximum
// consecutive 1's in a binary circular array
static int getMaxLength(int[] arr, int n)
{
// Starting index
int start = 0;
// To store the maximum length of the
// prefix of the given array with all 1s
int preCnt = 0;
while (start < n && arr[start] == 1) {
preCnt++;
start++;
}
// Ending index
int end = n - 1;
// To store the maximum length of the
// suffix of the given array with all 1s
int suffCnt = 0;
while (end >= 0 && arr[end] == 1) {
suffCnt++;
end--;
}
// The array contains all 1s
if (start > end)
return n;
// Find the maximum length subarray
// with all 1s from the remaining not
// yet traversed subarray
int midCnt = 0;
// To store the result for middle 1s
int result = 0;
for (int i = start; i <= end; i++) {
if (arr[i] == 1) {
midCnt++;
result = Math.Max(result, midCnt);
}
else {
midCnt = 0;
}
}
// (preCnt + suffCnt) is the subarray when
// the given array is assumed to be circular
return Math.Max(result, preCnt + suffCnt);
}
// Driver code
public static void Main()
{
int[] arr = new int[] { 1, 1, 0, 0, 1, 0,
1, 0, 1, 1, 1, 0 };
int n = arr.Length;
Console.WriteLine(getMaxLength(arr, n));
}
}
// This code is contributed by Code_Mech.
Javascript
<script>
// javascript program to count maximum consecutive
// 1's in a binary circular array
// Function to return the count of maximum
// consecutive 1's in a binary circular array
function getMaxLength(arr , n)
{
// Starting index
var start = 0;
// To store the maximum length of the
// prefix of the given array with all 1s
var preCnt = 0;
while (start < n && arr[start] == 1) {
preCnt++;
start++;
}
// Ending index
var end = n - 1;
// To store the maximum length of the
// suffix of the given array with all 1s
var suffCnt = 0;
while (end >= 0 && arr[end] == 1) {
suffCnt++;
end--;
}
// The array contains all 1s
if (start > end)
return n;
// Find the maximum length subarray
// with all 1s from the remaining not
// yet traversed subarray
var midCnt = 0;
// To store the result for middle 1s
var result = 0;
for (i = start; i <= end; i++) {
if (arr[i] == 1) {
midCnt++;
result = Math.max(result, midCnt);
} else {
midCnt = 0;
}
}
// (preCnt + suffCnt) is the subarray when
// the given array is assumed to be circular
return Math.max(result, preCnt + suffCnt);
}
// Driver code
var arr = [ 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 ];
var n = arr.length;
document.write(getMaxLength(arr, n));
// This code is contributed by umadevi9616
</script>
Producción
6
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es el número de elementos de la array.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.