Dado un arreglo A[ ] de N enteros no negativos, la tarea es encontrar la longitud del subarreglo más largo tal que todos los elementos en ese subarreglo sean pares o impares.
Ejemplos:
Entrada: A[] = {2, 5, 7, 2, 4, 6, 8, 3}
Salida: 4
Explicación: el subconjunto {2, 4, 6, 8} de longitud 4 tiene todos los elementos paresEntrada: A[] = {2, 3, 2, 5, 7, 3}
Salida: 3
Explicación: el subconjunto {5, 7, 3} de longitud 3 tiene todos los elementos impares
Enfoque ingenuo: un enfoque ingenuo para resolver este problema es considerar todos los subconjuntos contiguos y, para cada subconjunto, verificar si todos los elementos son pares o impares. El más largo de ellos será la respuesta.
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(1)
Enfoque eficiente: la idea principal para resolver este problema es usar la programación dinámica (tiene ambas propiedades: subestructura óptima y subproblemas superpuestos ) de modo que si hay algunos elementos impares contiguos, entonces el siguiente elemento impar aumentará la longitud de ese array contigua por uno. Y esto también es cierto para los elementos pares. Siga los pasos a continuación para resolver el problema:
- Inicialice una array dp[ ] donde dp[i] almacena la longitud de la sub-array que termina en A[i] .
- Inicialice dp[0] con 1 .
- Inicialice la variable ans como 1 para almacenar la respuesta.
- Iterar sobre el rango [1, N] usando la variable i y realizar los siguientes pasos:
- Si A[i]%2 es igual a A[i-1]%2, establezca el valor de dp[i] como dp[i-1]+1.
- De lo contrario, establezca el valor de dp[i] en 1.
- Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
- Establezca el valor de ans como el máximo de ans o dp[i].
- Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate longest substring
// with odd or even elements
int LongestOddEvenSubarray(int A[], int N)
{
// Initializing dp[]
int dp[N];
// Initializing dp[0] with 1
dp[0] = 1;
// ans will store the final answer
int ans = 1;
// Traversing the array from index 1 to N - 1
for (int i = 1; i < N; i++) {
// Checking both current and previous element
// is even or odd
if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0)
|| (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) {
// Updating dp[i] with dp[i-1] + 1
dp[i] = dp[i - 1] + 1;
}
else
dp[i] = 1;
}
for (int i = 0; i < N; i++)
// Storing max element to ans
ans = max(ans, dp[i]);
// Returning the final answer
return ans;
}
// Driver Code
int main()
{
// Input
int A[] = { 2, 5, 7, 2, 4, 6, 8, 3 };
int N = sizeof(A) / sizeof(A[0]);
// Function call
cout << LongestOddEvenSubarray(A, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to calculate longest substring
// with odd or even elements
static int LongestOddEvenSubarray(int A[], int N)
{
// Initializing dp[]
int dp[] = new int[N];
// Initializing dp[0] with 1
dp[0] = 1;
// ans will store the final answer
int ans = 1;
// Traversing the array from index 1 to N - 1
for (int i = 1; i < N; i++) {
// Checking both current and previous element
// is even or odd
if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0)
|| (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) {
// Updating dp[i] with dp[i-1] + 1
dp[i] = dp[i - 1] + 1;
}
else
dp[i] = 1;
}
for (int i = 0; i < N; i++)
// Storing max element to ans
ans = Math.max(ans, dp[i]);
// Returning the final answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Input
int A[] = { 2, 5, 7, 2, 4, 6, 8, 3 };
int N = A.length;
// Function call
System.out.println(LongestOddEvenSubarray(A, N));
}
}
// This code is contributed by Potta Lokesh
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate longest substring
// with odd or even elements
static int LongestOddEvenSubarray(int[] A, int N)
{
// Initializing dp[]
int[] dp = new int[N];
// Initializing dp[0] with 1
dp[0] = 1;
// ans will store the final answer
int ans = 1;
// Traversing the array from index 1 to N - 1
for (int i = 1; i < N; i++) {
// Checking both current and previous element
// is even or odd
if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0)
|| (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) {
// Updating dp[i] with dp[i-1] + 1
dp[i] = dp[i - 1] + 1;
}
else
dp[i] = 1;
}
for (int i = 0; i < N; i++)
// Storing max element to ans
ans = Math.Max(ans, dp[i]);
// Returning the final answer
return ans;
}
// Driver Code
public static void Main()
{
// Input
int[] A = { 2, 5, 7, 2, 4, 6, 8, 3 };
int N = A.Length;
// Function call
Console.Write(LongestOddEvenSubarray(A, N));
}
}
// This code is contributed by target_2.
Python3
# Python 3 implementation for the above approach # Function to calculate longest substring # with odd or even elements def LongestOddEvenSubarray(A, N): # Initializing dp[] dp = [0 for i in range(N)] # Initializing dp[0] with 1 dp[0] = 1 # ans will store the final answer ans = 1 # Traversing the array from index 1 to N - 1 for i in range(1, N, 1): # Checking both current and previous element # is even or odd if ((A[i] % 2 == 0 and A[i - 1] % 2 == 0) or (A[i] % 2 != 0 and A[i - 1] % 2 != 0)): # Updating dp[i] with dp[i-1] + 1 dp[i] = dp[i - 1] + 1 else: dp[i] = 1 for i in range(N): # Storing max element to ans ans = max(ans, dp[i]) # Returning the final answer return ans # Driver Code if __name__ == '__main__': # Input A = [2, 5, 7, 2, 4, 6, 8, 3] N = len(A) # Function call print(LongestOddEvenSubarray(A, N)) # This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript implementation for the above approach
// Function to calculate longest substring
// with odd or even elements
function LongestOddEvenSubarray(A, N)
{
// Initializing dp[]
let dp = new Array(N);
// Initializing dp[0] with 1
dp[0] = 1;
// ans will store the final answer
let ans = 1;
// Traversing the array from index 1 to N - 1
for (let i = 1; i < N; i++)
{
// Checking both current and previous element
// is even or odd
if (
(A[i] % 2 == 0 && A[i - 1] % 2 == 0) ||
(A[i] % 2 != 0 && A[i - 1] % 2 != 0)
) {
// Updating dp[i] with dp[i-1] + 1
dp[i] = dp[i - 1] + 1;
} else dp[i] = 1;
}
for (let i = 0; i < N; i++)
// Storing max element to ans
ans = Math.max(ans, dp[i]);
// Returning the final answer
return ans;
}
// Driver Code
// Input
let A = [2, 5, 7, 2, 4, 6, 8, 3];
let N = A.length;
// Function call
document.write(LongestOddEvenSubarray(A, N));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Optimización del espacio: es posible optimizar aún más la complejidad del espacio del enfoque anterior al observar que, para calcular dp[i] , solo el valor de dp[i-1] es relevante. Entonces, almacene dp[i-1] en una variable y actualice la variable en cada iteración. Además, actualice la respuesta en cada iteración. Siga los pasos a continuación para resolver el problema:
- Inicialice las variables dp como 1 para almacenar la longitud del subarreglo hasta i-1 y ans como 1 para almacenar la respuesta.
- Iterar sobre el rango [1, N] usando la variable i y realizar los siguientes pasos:
- Si A[i]%2 es igual a A[i-1]%2, establezca el valor de dp como dp+1 y establezca el valor de ans como el máximo de ans o dp.
- De lo contrario, establezca el valor de dp en 1.
- Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate longest substring
// with odd or even elements
int LongestOddEvenSubarray(int A[], int N)
{
// Initializing dp
int dp;
// Initializing dp with 1
dp = 1;
// ans will store the final answer
int ans = 1;
// Traversing the array from index 1 to N - 1
for (int i = 1; i < N; i++) {
// Checking both current and previous element
// is even or odd
if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0)
|| (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) {
// Updating dp with (previous dp value) + 1
dp = dp + 1;
// Storing max element so far to ans
ans = max(ans, dp);
}
else
dp = 1;
}
// Returning the final answer
return ans;
}
// Driver code
int main()
{
// Input
int A[] = { 2, 5, 7, 2, 4, 6, 8, 3 };
int N = sizeof(A) / sizeof(A[0]);
// Function call
cout << LongestOddEvenSubarray(A, N);
return 0;
}
Java
// Java implementation for the above approach
import java.util.*;
class GFG
{
// Function to calculate longest subString
// with odd or even elements
static int LongestOddEvenSubarray(int A[], int N)
{
// Initializing dp
int dp;
// Initializing dp with 1
dp = 1;
// ans will store the final answer
int ans = 1;
// Traversing the array from index 1 to N - 1
for (int i = 1; i < N; i++) {
// Checking both current and previous element
// is even or odd
if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0)
|| (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) {
// Updating dp with (previous dp value) + 1
dp = dp + 1;
// Storing max element so far to ans
ans = Math.max(ans, dp);
}
else
dp = 1;
}
// Returning the final answer
return ans;
}
// Driver code
public static void main(String[] args)
{
// Input
int A[] = { 2, 5, 7, 2, 4, 6, 8, 3 };
int N = A.length;
// Function call
System.out.print(LongestOddEvenSubarray(A, N));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python implementation for the above approach # Function to calculate longest substring # with odd or even elements def LongestOddEvenSubarray(A, N): # Initializing dp # Initializing dp with 1 dp = 1 # ans will store the final answer ans = 1 # Traversing the array from index 1 to N - 1 for i in range(1, N): # Checking both current and previous element # is even or odd if ((A[i] % 2 == 0 and A[i - 1] % 2 == 0) or (A[i] % 2 != 0 and A[i - 1] % 2 != 0)): # Updating dp with (previous dp value) + 1 dp = dp + 1 # Storing max element so far to ans ans = max(ans, dp) else: dp = 1 # Returning the final answer return ans # Driver code # Input A = [2, 5, 7, 2, 4, 6, 8, 3 ] N = len(A) # Function call print(LongestOddEvenSubarray(A, N)) # This code is contributed by shivani
C#
// C# implementation for the above approach
using System;
public class GFG
{
// Function to calculate longest subString
// with odd or even elements
static int longestOddEvenSubarray(int []A, int N)
{
// Initializing dp
int dp;
// Initializing dp with 1
dp = 1;
// ans will store the readonly answer
int ans = 1;
// Traversing the array from index 1 to N - 1
for (int i = 1; i < N; i++) {
// Checking both current and previous element
// is even or odd
if ((A[i] % 2 == 0 && A[i - 1] % 2 == 0)
|| (A[i] % 2 != 0 && A[i - 1] % 2 != 0)) {
// Updating dp with (previous dp value) + 1
dp = dp + 1;
// Storing max element so far to ans
ans = Math.Max(ans, dp);
}
else
dp = 1;
}
// Returning the readonly answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
// Input
int []A = { 2, 5, 7, 2, 4, 6, 8, 3 };
int N = A.Length;
// Function call
Console.Write(longestOddEvenSubarray(A, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation for the above approach
// Function to calculate longest substring
// with odd or even elements
function LongestOddEvenSubarray(A, N) {
// Initializing dp
let dp;
// Initializing dp with 1
dp = 1;
// ans will store the final answer
let ans = 1;
// Traversing the array from index 1 to N - 1
for (let i = 1; i < N; i++) {
// Checking both current and previous element
// is even or odd
if (
(A[i] % 2 == 0 && A[i - 1] % 2 == 0) ||
(A[i] % 2 != 0 && A[i - 1] % 2 != 0)
) {
// Updating dp with (previous dp value) + 1
dp = dp + 1;
// Storing max element so far to ans
ans = Math.max(ans, dp);
} else dp = 1;
}
// Returning the final answer
return ans;
}
// Driver code
// Input
let A = [2, 5, 7, 2, 4, 6, 8, 3];
let N = A.length;
// Function call
document.write(LongestOddEvenSubarray(A, N));
</script>
Producción
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ganapati_biswas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA