Dado un arreglo binario arr[] , la tarea es encontrar la longitud del subarreglo más largo del arreglo dado, de modo que si el subarreglo se divide en dos subarreglos del mismo tamaño, ambos contienen todos 0 o todos 1 . Por ejemplo, los dos subarreglos deben tener la forma {0, 0, 0, 0} y {1, 1, 1, 1} o {1, 1, 1} y {0, 0, 0} y no {0, 0, 0} y {0, 0, 0}
Ejemplos:
Entrada: arr[] = {1, 1, 1, 0, 0, 1, 1}
Salida: 4
{1, 1, 0, 0} y {0, 0, 1, 1} son la longitud máxima válida sub- arreglosEntrada: arr[] = {1, 1, 0, 0, 0, 1, 1, 1, 1}
Salida: 6
{0, 0, 0, 1, 1, 1} es el único subarreglo válido con máximo longitud.
Enfoque: Por cada dos elementos consecutivos de la array, diga arr[i] y arr[j] donde j = i + 1 , trátelos como los dos elementos del medio de la sub-array requerida. Para que este subconjunto sea un subconjunto válido, arr[i] no debe ser igual a arr[j] . Si puede ser un subarreglo válido, entonces su tamaño es 2 . Ahora, intente extender este subarreglo a un tamaño mayor disminuyendo i e incrementando j al mismo tiempo y todos los elementos antes del índice i y después del índice j deben ser iguales a arr[i] y arr[j]respectivamente. Imprima el tamaño del subarreglo más largo encontrado hasta el momento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum length
// of the required sub-array
int maxLength(int arr[], int n)
{
int maxLen = 0;
// For the first consecutive
// pair of elements
int i = 0;
int j = i + 1;
// While a consecutive pair
// can be selected
while (j < n) {
// If current pair forms a
// valid sub-array
if (arr[i] != arr[j]) {
// 2 is the length of the
// current sub-array
maxLen = max(maxLen, 2);
// To extend the sub-array both ways
int l = i - 1;
int r = j + 1;
// While elements at indices l and r
// are part of a valid sub-array
while (l >= 0 && r < n && arr[l] == arr[i]
&& arr[r] == arr[j]) {
l--;
r++;
}
// Update the maximum length so far
maxLen = max(maxLen, 2 * (r - j));
}
// Select the next consecutive pair
i++;
j = i + 1;
}
// Return the maximum length
return maxLen;
}
// Driver code
int main()
{
int arr[] = { 1, 1, 1, 0, 0, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxLength(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Function to return the maximum length
// of the required sub-array
static int maxLength(int arr[], int n)
{
int maxLen = 0;
// For the first consecutive
// pair of elements
int i = 0;
int j = i + 1;
// While a consecutive pair
// can be selected
while (j < n) {
// If current pair forms a
// valid sub-array
if (arr[i] != arr[j]) {
// 2 is the length of the
// current sub-array
maxLen = Math.max(maxLen, 2);
// To extend the sub-array both ways
int l = i - 1;
int r = j + 1;
// While elements at indices l and r
// are part of a valid sub-array
while (l >= 0 && r < n && arr[l] == arr[i] && arr[r] == arr[j]) {
l--;
r++;
}
// Update the maximum length so far
maxLen = Math.max(maxLen, 2 * (r - j));
}
// Select the next consecutive pair
i++;
j = i + 1;
}
// Return the maximum length
return maxLen;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 1, 1, 0, 0, 1, 1 };
int n = arr.length;
System.out.println(maxLength(arr, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the maximum length # of the required sub-array def maxLength(arr, n): maxLen = 0 # For the first consecutive # pair of elements i = 0 j = i + 1 # While a consecutive pair # can be selected while (j < n): # If current pair forms a # valid sub-array if (arr[i] != arr[j]): # 2 is the length of the # current sub-array maxLen = max(maxLen, 2) # To extend the sub-array both ways l = i - 1 r = j + 1 # While elements at indices l and r # are part of a valid sub-array while (l >= 0 and r < n and arr[l] == arr[i] and arr[r] == arr[j]): l-= 1 r+= 1 # Update the maximum length so far maxLen = max(maxLen, 2 * (r - j)) # Select the next consecutive pair i+= 1 j = i + 1 # Return the maximum length return maxLen # Driver code arr =[1, 1, 1, 0, 0, 1, 1] n = len(arr) print(maxLength(arr, n)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG {
// Function to return the maximum length
// of the required sub-array
static int maxLength(int[] arr, int n)
{
int maxLen = 0;
// For the first consecutive
// pair of elements
int i = 0;
int j = i + 1;
// While a consecutive pair
// can be selected
while (j < n) {
// If current pair forms a
// valid sub-array
if (arr[i] != arr[j]) {
// 2 is the length of the
// current sub-array
maxLen = Math.Max(maxLen, 2);
// To extend the sub-array both ways
int l = i - 1;
int r = j + 1;
// While elements at indices l and r
// are part of a valid sub-array
while (l >= 0 && r < n && arr[l] == arr[i] && arr[r] == arr[j]) {
l--;
r++;
}
// Update the maximum length so far
maxLen = Math.Max(maxLen, 2 * (r - j));
}
// Select the next consecutive pair
i++;
j = i + 1;
}
// Return the maximum length
return maxLen;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 1, 1, 1, 0, 0, 1, 1 };
int n = arr.Length;
Console.WriteLine(maxLength(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the maximum length
// of the required sub-array
function maxLength(arr, n)
{
let maxLen = 0;
// For the first consecutive
// pair of elements
let i = 0;
let j = i + 1;
// While a consecutive pair
// can be selected
while (j < n) {
// If current pair forms a
// valid sub-array
if (arr[i] != arr[j]) {
// 2 is the length of the
// current sub-array
maxLen = Math.max(maxLen, 2);
// To extend the sub-array both ways
let l = i - 1;
let r = j + 1;
// While elements at indices l and r
// are part of a valid sub-array
while (l >= 0 && r < n && arr[l] == arr[i]
&& arr[r] == arr[j]) {
l--;
r++;
}
// Update the maximum length so far
maxLen = Math.max(maxLen, 2 * (r - j));
}
// Select the next consecutive pair
i++;
j = i + 1;
}
// Return the maximum length
return maxLen;
}
// Driver code
let arr = [ 1, 1, 1, 0, 0, 1, 1 ];
let n = arr.length;
document.write(maxLength(arr, n));
</script>
Producción:
4
Enfoque alternativo: podemos mantener la longitud máxima de los elementos similares anteriores e intentar formar un subarreglo con el siguiente elemento contiguo diferente y maximizar la longitud del subarreglo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Function to return the maximum length
// of the required sub-array
int maxLength(int a[], int n)
{
// To store the maximum length
// for a valid subarray
int maxLen = 0;
// To store the count of contiguous
// similar elements for previous
// group and the current group
int prev_cnt = 0, curr_cnt = 1;
for (int i = 1; i < n; i++) {
// If current element is equal to
// the previous element then it is
// a part of the same group
if (a[i] == a[i - 1])
curr_cnt++;
// Else update the previous group
// and start counting elements
// for the new group
else {
prev_cnt = curr_cnt;
curr_cnt = 1;
}
// Update the maximum possible length for a group
maxLen = max(maxLen, min(prev_cnt, curr_cnt));
}
// Return the maximum length of the valid subarray
return (2 * maxLen);
}
// Driver code
int main()
{
int arr[] = { 1, 1, 1, 0, 0, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxLength(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the maximum length
// of the required sub-array
static int maxLength(int a[], int n)
{
// To store the maximum length
// for a valid subarray
int maxLen = 0;
// To store the count of contiguous
// similar elements for previous
// group and the current group
int prev_cnt = 0, curr_cnt = 1;
for (int i = 1; i < n; i++)
{
// If current element is equal to
// the previous element then it is
// a part of the same group
if (a[i] == a[i - 1])
curr_cnt++;
// Else update the previous group
// and start counting elements
// for the new group
else
{
prev_cnt = curr_cnt;
curr_cnt = 1;
}
// Update the maximum possible length for a group
maxLen = Math.max(maxLen,
Math.min(prev_cnt, curr_cnt));
}
// Return the maximum length
// of the valid subarray
return (2 * maxLen);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 1, 1, 0, 0, 1, 1 };
int n = arr.length;
System.out.println(maxLength(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return the maximum length # of the required sub-array def maxLength(a, n): # To store the maximum length # for a valid subarray maxLen = 0; # To store the count of contiguous # similar elements for previous # group and the current group prev_cnt = 0; curr_cnt = 1; for i in range(1, n): # If current element is equal to # the previous element then it is # a part of the same group if (a[i] == a[i - 1]): curr_cnt += 1; # Else update the previous group # and start counting elements # for the new group else: prev_cnt = curr_cnt; curr_cnt = 1; # Update the maximum possible # length for a group maxLen = max(maxLen, min(prev_cnt, curr_cnt)); # Return the maximum length # of the valid subarray return (2 * maxLen); # Driver code arr = [ 1, 1, 1, 0, 0, 1, 1 ]; n = len(arr); print(maxLength(arr, n)); # This code is contributed by Rajput-Ji
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the maximum length
// of the required sub-array
static int maxLength(int[] a, int n)
{
// To store the maximum length
// for a valid subarray
int maxLen = 0;
// To store the count of contiguous
// similar elements for previous
// group and the current group
int prev_cnt = 0, curr_cnt = 1;
for (int i = 1; i < n; i++)
{
// If current element is equal to
// the previous element then it is
// a part of the same group
if (a[i] == a[i - 1])
curr_cnt++;
// Else update the previous group
// and start counting elements
// for the new group
else
{
prev_cnt = curr_cnt;
curr_cnt = 1;
}
// Update the maximum possible length for a group
maxLen = Math.Max(maxLen,
Math.Min(prev_cnt, curr_cnt));
}
// Return the maximum length
// of the valid subarray
return (2 * maxLen);
}
// Driver code
public static void Main()
{
int[] arr = { 1, 1, 1, 0, 0, 1, 1 };
int n = arr.Length;
Console.WriteLine(maxLength(arr, n));
}
}
// This code is contributed by Code_Mech.
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the maximum length
// of the required sub-array
function maxLength(a, n)
{
// To store the maximum length
// for a valid subarray
let maxLen = 0;
// To store the count of contiguous
// similar elements for previous
// group and the current group
let prev_cnt = 0, curr_cnt = 1;
for (let i = 1; i < n; i++) {
// If current element is equal to
// the previous element then it is
// a part of the same group
if (a[i] == a[i - 1])
curr_cnt++;
// Else update the previous group
// and start counting elements
// for the new group
else {
prev_cnt = curr_cnt;
curr_cnt = 1;
}
// Update the maximum possible length for a group
maxLen = Math.max(maxLen, Math.min(prev_cnt, curr_cnt));
}
// Return the maximum length of the valid subarray
return (2 * maxLen);
}
// Driver code
let arr = [ 1, 1, 1, 0, 0, 1, 1 ];
let n = arr.length;
document.write(maxLength(arr, n));
</script>
Producción:
4
Publicación traducida automáticamente
Artículo escrito por Vidhayak_Chacha y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA