Longitud máxima del subarreglo que consta del mismo tipo de elemento en ambas mitades del subarreglo

Dada una array arr[] de N enteros, la tarea es encontrar la longitud máxima de la subarray que consta del mismo tipo de elemento en ambas mitades de la subarray. Además, los elementos de ambas mitades difieren entre sí.

Ejemplos:

Entrada: arr[] = {2, 3, 4, 4, 5, 5, 6, 7, 8, 10}
Salida: 4
Explicación:
{2, 3}, {3, 4}, {4, 4, 5 , 5}, {5, 6}, etc., son los subconjuntos válidos donde ambas mitades tienen un solo tipo de elemento. 
{4, 4, 5, 5} es el subarreglo que tiene la longitud máxima.
Por lo tanto, la salida es 4. 

Entrada: arr[] = {1, 7, 7, 10, 10, 7, 7, 7, 8, 8, 8, 9}
Salida: 6
Explicación:
{1, 7}, {7, 7, 10, 10 }, {7, 7, 7, 8, 8, 8}, {8, 9}, etc., son los sub-arreglos válidos donde ambas mitades tienen un solo tipo de elemento. 
{7, 7, 7, 8, 8, 8} es el subconjunto que tiene la longitud máxima.
Por lo tanto, la salida es 6. 

 

Enfoque ingenuo: la idea ingenua es generar todos los subarreglos posibles y verificar que cualquier subarreglo con la longitud máxima se pueda dividir en dos mitades de modo que todos los elementos en ambas mitades sean iguales.

Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)

Enfoque Eficiente: Para resolver este problema la idea es utilizar el concepto de Suma Prefijo . Siga los pasos a continuación para resolver el problema: 

  1. Recorra la array desde el principio en la dirección de avance y almacene la ocurrencia continua de un número entero para cada índice en una array hacia adelante [].
  2. De manera similar, recorra la array desde el final en la dirección inversa y almacene la ocurrencia continua de un número entero para cada índice en una array hacia atrás [] .
  3. Almacene el máximo de min(hacia adelante[i], hacia atrás[i+1])*2, para todo el índice donde arr[i]!=arr[i+1] .
  4. Imprime el valor obtenido en el paso anterior.

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 that finds the maximum
// length of the sub-array that
// contains equal element on both
// halves of sub-array
void maxLengthSubArray(int A[], int N)
{
 
    // To store continuous occurrence
    // of the element
    int forward[N], backward[N];
 
    // To store continuous
    // forward occurrence
    for (int i = 0; i < N; i++) {
 
        if (i == 0
            || A[i] != A[i - 1]) {
            forward[i] = 1;
        }
        else
            forward[i] = forward[i - 1] + 1;
    }
 
    // To store continuous
    // backward occurrence
    for (int i = N - 1; i >= 0; i--) {
 
        if (i == N - 1
            || A[i] != A[i + 1]) {
            backward[i] = 1;
        }
        else
            backward[i] = backward[i + 1] + 1;
    }
 
    // To store the maximum length
    int ans = 0;
 
    // Find maximum length
    for (int i = 0; i < N - 1; i++) {
 
        if (A[i] != A[i + 1])
            ans = max(ans,
                    min(forward[i],
                        backward[i + 1])
                        * 2);
    }
 
    // Print the result
    cout << ans;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 1, 2, 3, 4, 4,
                4, 6, 6, 6, 9 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    maxLengthSubArray(arr, N);
    return 0;
}

Java

// Java program for the above approach         
class GFG{         
            
// Function that finds the maximum         
// length of the sub-array that         
// contains equal element on both         
// halves of sub-array         
static void maxLengthSubArray(int A[], int N)         
{
     
    // To store continuous occurrence         
    // of the element         
    int forward[] = new int[N];         
    int backward[] = new int[N];         
     
    // To store continuous         
    // forkward occurrence         
    for(int i = 0; i < N; i++)
    {
        if (i == 0 || A[i] != A[i - 1])
        {         
            forward[i] = 1;         
        }         
        else         
            forward[i] = forward[i - 1] + 1;         
    }         
     
    // To store continuous         
    // backward occurrence         
    for(int i = N - 1; i >= 0; i--)
    {
        if (i == N - 1 || A[i] != A[i + 1])
        {         
            backward[i] = 1;         
        }         
        else         
            backward[i] = backward[i + 1] + 1;         
    }         
            
    // To store the maximum length         
    int ans = 0;         
        
    // Find maximum length         
    for(int i = 0; i < N - 1; i++)
    {         
        if (A[i] != A[i + 1])         
            ans = Math.max(ans,         
                           Math.min(forward[i],         
                                    backward[i + 1]) * 2);         
    }         
     
    // Print the result         
    System.out.println(ans);         
}         
            
// Driver Code         
public static void main(String[] args)
{         
     
    // Given array         
    int arr[] = { 1, 2, 3, 4, 4,         
                  4, 6, 6, 6, 9 };         
            
    // Size of the array         
    int N = arr.length;         
            
    // Function call         
    maxLengthSubArray(arr, N);         
}         
}
 
// This code is contributed by rutvik_56

Python3

# Python3 program for the above approach
 
# Function that finds the maximum
# length of the sub-array that
# contains equal element on both
# halves of sub-array
def maxLengthSubArray(A, N):
 
    # To store continuous occurrence
    # of the element
    forward = [0] * N
    backward = [0] * N
 
    # To store continuous
    # forward occurrence
    for i in range(N):
            if i == 0 or A[i] != A[i - 1]:
                forward[i] = 1
            else:
                forward[i] = forward[i - 1] + 1
 
    # To store continuous
    # backward occurrence
    for i in range(N - 1, -1, -1):
        if i == N - 1 or A[i] != A[i + 1]:
            backward[i] = 1
        else:
            backward[i] = backward[i + 1] + 1
             
    # To store the maximum length
    ans = 0
 
    # Find maximum length
    for i in range(N - 1):
        if (A[i] != A[i + 1]):
            ans = max(ans,
                    min(forward[i],
                        backward[i + 1]) * 2);
 
    # Print the result
    print(ans)
 
# Driver Code
 
# Given array
arr = [ 1, 2, 3, 4, 4, 4, 6, 6, 6, 9 ]
 
# Size of the array
N = len(arr)
 
# Function call
maxLengthSubArray(arr, N)
 
# This code is contributed by yatinagg

C#

// C# program for the above approach         
using System;
class GFG{         
            
// Function that finds the maximum         
// length of the sub-array that         
// contains equal element on both         
// halves of sub-array         
static void maxLengthSubArray(int []A, int N)         
{
     
    // To store continuous occurrence         
    // of the element         
    int []forward = new int[N];         
    int []backward = new int[N];         
     
    // To store continuous         
    // forkward occurrence         
    for(int i = 0; i < N; i++)
    {
        if (i == 0 || A[i] != A[i - 1])
        {         
            forward[i] = 1;         
        }         
        else         
            forward[i] = forward[i - 1] + 1;         
    }         
     
    // To store continuous         
    // backward occurence         
    for(int i = N - 1; i >= 0; i--)
    {
        if (i == N - 1 || A[i] != A[i + 1])
        {         
            backward[i] = 1;         
        }         
        else         
            backward[i] = backward[i + 1] + 1;         
    }         
            
    // To store the maximum length         
    int ans = 0;         
        
    // Find maximum length         
    for(int i = 0; i < N - 1; i++)
    {         
        if (A[i] != A[i + 1])         
            ans = Math.Max(ans,         
                           Math.Min(forward[i],         
                                    backward[i + 1]) * 2);         
    }         
     
    // Print the result         
    Console.WriteLine(ans);         
}         
            
// Driver Code         
public static void Main(String[] args)
{         
     
    // Given array         
    int []arr = { 1, 2, 3, 4, 4,         
                  4, 6, 6, 6, 9 };         
            
    // Size of the array         
    int N = arr.Length;         
            
    // Function call         
    maxLengthSubArray(arr, N);         
}         
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript program for the above approach
 
// Function that finds the maximum        
// length of the sub-array that        
// contains equal element on both        
// halves of sub-array        
function maxLengthSubArray(A, N)        
{
      
    // To store continuous occurrence        
    // of the element        
    let forward = Array.from({length: N}, (_, i) => 0);       
    let backward = Array.from({length: N}, (_, i) => 0);   
      
    // To store continuous        
    // forkward occurrence        
    for(let i = 0; i < N; i++)
    {
        if (i == 0 || A[i] != A[i - 1])
        {        
            forward[i] = 1;        
        }        
        else        
            forward[i] = forward[i - 1] + 1;        
    }        
      
    // To store continuous        
    // backward occurrence        
    for(let i = N - 1; i >= 0; i--)
    {
        if (i == N - 1 || A[i] != A[i + 1])
        {        
            backward[i] = 1;        
        }        
        else        
            backward[i] = backward[i + 1] + 1;        
    }        
             
    // To store the maximum length        
    let ans = 0;        
         
    // Find maximum length        
    for(let i = 0; i < N - 1; i++)
    {        
        if (A[i] != A[i + 1])        
            ans = Math.max(ans,        
                           Math.min(forward[i],        
                                    backward[i + 1]) * 2);        
    }        
      
    // Print the result        
    document.write(ans);        
}        
    
 
// Driver Code
     
    // Given array        
    let arr = [ 1, 2, 3, 4, 4,        
                  4, 6, 6, 6, 9 ];        
             
    // Size of the array        
    let N = arr.length;        
             
    // Function call        
    maxLengthSubArray(arr, N);
 
</script>
Producción: 

6

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

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