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:
- 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 [].
- 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 [] .
- 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] .
- 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>
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)