Dada una array de N elementos. La tarea es encontrar la longitud del subarreglo más largo tal que la suma del subarreglo sea par.
Ejemplos:
Input : N = 6, arr[] = {1, 2, 3, 2, 1, 4}
Output : 5
Explanation: In the example the subarray
in range [2, 6] has sum 12 which is even,
so the length is 5.
Input : N = 4, arr[] = {1, 2, 3, 2}
Output : 4
Enfoque: primero verifique si la suma total de la array es par. Si la suma total de la array es par, la respuesta será N.
Si la suma total de la array no es par, significa que es impar. Entonces, la idea es encontrar un elemento impar de la array de tal manera que, excluyendo ese elemento y comparando la longitud de ambas partes de la array, podamos obtener la longitud máxima de la subarreglo con una suma par.
Es obvio que el subarreglo con suma par existirá en el rango [1, x) o (x, N],
donde 1 <= x <= N, y arr[x] es ODD.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find length of the longest
// subarray such that sum of the
// subarray is even
int maxLength(int a[], int n)
{
int sum = 0, len = 0;
// Check if sum of complete array is even
for (int i = 0; i < n; i++)
sum += a[i];
if (sum % 2 == 0) // total sum is already even
return n;
// Find an index i such the a[i] is odd
// and compare length of both halfs excluding
// a[i] to find max length subarray
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 1)
len = max(len, max(n - i - 1, i));
}
return len;
}
// Driver Code
int main()
{
int a[] = { 1, 2, 3, 2 };
int n = sizeof(a) / sizeof(a[0]);
cout << maxLength(a, n) << "\n";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to find length of the longest
// subarray such that sum of the
// subarray is even
static int maxLength(int a[], int n)
{
int sum = 0, len = 0;
// Check if sum of complete array is even
for (int i = 0; i < n; i++)
{
sum += a[i];
}
if (sum % 2 == 0) // total sum is already even
{
return n;
}
// Find an index i such the a[i] is odd
// and compare length of both halfs excluding
// a[i] to find max length subarray
for (int i = 0; i < n; i++)
{
if (a[i] % 2 == 1)
{
len = Math.max(len, Math.max(n - i - 1, i));
}
}
return len;
}
// Driver Code
public static void main(String[] args)
{
int a[] = {1, 2, 3, 2};
int n = a.length;
System.out.println(maxLength(a, n));
}
}
// This code has been contributed by 29AjayKumar
Python
# Python3 implementation of the above approach # Function to find Length of the longest # subarray such that Sum of the # subarray is even def maxLength(a, n): Sum = 0 Len = 0 # Check if Sum of complete array is even for i in range(n): Sum += a[i] if (Sum % 2 == 0): # total Sum is already even return n # Find an index i such the a[i] is odd # and compare Length of both halfs excluding # a[i] to find max Length subarray for i in range(n): if (a[i] % 2 == 1): Len = max(Len, max(n - i - 1, i)) return Len # Driver Code a= [1, 2, 3, 2] n = len(a) print(maxLength(a, n)) # This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find length of the longest
// subarray such that sum of the
// subarray is even
static int maxLength(int []a, int n)
{
int sum = 0, len = 0;
// Check if sum of complete array is even
for (int i = 0; i < n; i++)
{
sum += a[i];
}
if (sum % 2 == 0) // total sum is already even
{
return n;
}
// Find an index i such the a[i] is odd
// and compare length of both halfs excluding
// a[i] to find max length subarray
for (int i = 0; i < n; i++)
{
if (a[i] % 2 == 1)
{
len = Math.Max(len, Math.Max(n - i - 1, i));
}
}
return len;
}
// Driver Code
static public void Main ()
{
int []a = {1, 2, 3, 2};
int n = a.Length;
Console.WriteLine(maxLength(a, n));
}
}
// This code has been contributed by ajit.
PHP
<?php
//PHP implementation of the above approach
// Function to find length of the longest
// subarray such that sum of the
// subarray is even
function maxLength($a, $n)
{
$sum = 0;
$len = 0;
// Check if sum of complete array is even
for ($i = 0; $i < $n; $i++)
$sum += $a[$i];
if ($sum % 2 == 0) // total sum is already even
return $n;
// Find an index i such the a[i] is odd
// and compare length of both halfs excluding
// a[i] to find max length subarray
for ($i = 0; $i < $n; $i++)
{
if ($a[$i] % 2 == 1)
$len = max($len, $max($n - $i - 1, $i));
}
return $len;
}
// Driver Code
$a = array (1, 2, 3, 2 );
$n = count($a);
echo maxLength($a, $n) , "\n";
// This code is contributed by akt_mit.
?>
Javascript
<script>
// Javascript implementation of the above approach
// Function to find length of the longest
// subarray such that sum of the
// subarray is even
function maxLength(a, n)
{
let sum = 0, len = 0;
// Check if sum of complete array is even
for (let i = 0; i < n; i++)
sum += a[i];
if (sum % 2 == 0) // total sum is already even
return n;
// Find an index i such the a[i] is odd
// and compare length of both halfs excluding
// a[i] to find max length subarray
for (let i = 0; i < n; i++) {
if (a[i] % 2 == 1)
len = Math.max(len, Math.max(n - i - 1, i));
}
return len;
}
// Driver Code
let a = [ 1, 2, 3, 2 ];
let n = a.length;
document.write(maxLength(a, n) + "<br>");
// This code is contributed by Mayank Tyagi
</script>
Producción:
4
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)