Dado un arreglo arr[] de tamaño N , la tarea es encontrar el elemento más grande en el subarreglo más largo que consiste solo en números pares o números impares .
Ejemplos:
Entrada: arr[] = { 2, 4, 6, 9, 10, 11 }
Salida: 6
Explicación:
El subarreglo más largo que consta solo de números pares o impares es { arr[0], arr[1], arr[2] }.
Dado que el elemento más grande del subarreglo es arr[2], la salida requerida es 6.Entrada: arr[] = { 3, 5, 7, 4, 9, 11, 13 }
Salida: 13
Explicación:
El subarreglo más largo que consta solo de números pares o impares es { {3, 5, 7 }, { 9, 11 , 13 } }.
Los elementos más grandes en los subarreglos son 7 y 13 respectivamente. 13 siendo el más grande, es la salida requerida.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos maxLen , para almacenar la longitud del subarreglo más largo obtenido hasta el i -ésimo índice, que contiene números pares o números impares solamente.
- Inicialice una variable, digamos Len , para almacenar la longitud del subarreglo actual hasta el i -ésimo elemento del arreglo, que consta solo de números pares o impares.
- Inicialice una variable, digamos MaxElem , para almacenar el elemento más grande del subarreglo más largo obtenido hasta el i -ésimo índice que consta solo de elementos pares o impares.
- Recorre la array usando la variable i . Para cada i -ésimo elemento de la array, verifique si arr[i] % 2 es igual a arr[i – 1] % 2 o no. Si se encuentra que es cierto, entonces incremente el valor de Len .
- De lo contrario, actualice el valor de Len = 1 .
- Si Len >= maxLen , actualice MaxElem = max(MaxElem, arr[i]) .
- Finalmente, imprima el valor de MaxElem .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
// Function to find the largest element
// of the longest subarray consisting
// only of odd or even elements only
int maxelementLongestSub(int arr[], int n)
{
// Stores largest element of the
// longest subarray till i-th index
int MaxElem = arr[0];
// Stores maximum length of the
// longest subarray till i-th index
int maxLen = 1;
// Stores length of the current
// subarray including the i-th element
int Len = 1;
// Stores largest element in
// current subarray
int Max = arr[0];
// Traverse the array
for (int i = 1; i < n; i++) {
// If arr[i] and arr[i - 1]
// are either even numbers
// or odd numbers
if (arr[i] % 2 == arr[i - 1] % 2) {
// Update Len
Len++;
// Update Max
if (arr[i] > Max)
Max = arr[i];
// If Len greater than
// maxLen
if (Len >= maxLen) {
maxLen = Len;
// Update MaxElem
if (Max >= MaxElem)
MaxElem = Max;
}
}
else {
// Update Len
Len = 1;
// Update Max
Max = arr[i];
// If Len greater
// than maxLen
if (Len >= maxLen) {
// Update maxLen
maxLen = Len;
// If Max greater
// than MaxElem
if (Max >= MaxElem) {
// Update MaxElem
MaxElem = Max;
}
}
}
}
return MaxElem;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 7, 8, 12, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxelementLongestSub(arr, n);
return 0;
}
C
// C program to implement
// the above approach
#include <stdio.h>
// Function to find the largest element
// of the longest subarray consisting
// only of odd or even elements only
int maxelementLongestSub(int arr[], int n)
{
// Stores largest element of the
// longest subarray till i-th index
int MaxElem = arr[0];
// Stores maximum length of the
// longest subarray till i-th index
int maxLen = 1;
// Stores length of the current
// subarray including the i-th element
int Len = 1;
// Stores largest element in
// current subarray
int Max = arr[0];
// Traverse the array
for(int i = 1; i < n; i++)
{
// If arr[i] and arr[i - 1]
// are either even numbers
// or odd numbers
if (arr[i] % 2 == arr[i - 1] % 2)
{
// Update Len
Len++;
// Update Max
if (arr[i] > Max)
Max = arr[i];
// If Len greater than
// maxLen
if (Len >= maxLen)
{
maxLen = Len;
// Update MaxElem
if (Max >= MaxElem)
MaxElem = Max;
}
}
else
{
// Update Len
Len = 1;
// Update Max
Max = arr[i];
// If Len greater
// than maxLen
if (Len >= maxLen)
{
// Update maxLen
maxLen = Len;
// If Max greater
// than MaxElem
if (Max >= MaxElem)
{
// Update MaxElem
MaxElem = Max;
}
}
}
}
return MaxElem;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 7, 8, 12, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", maxelementLongestSub(arr, n));
return 0;
}
// This code is contributed by sourav singh
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to find the largest element
// of the longest subarray consisting
// only of odd or even elements only
static int maxelementLongestSub(int arr[], int n)
{
// Stores largest element of the
// longest subarray till i-th index
int MaxElem = arr[0];
// Stores maximum length of the
// longest subarray till i-th index
int maxLen = 1;
// Stores length of the current
// subarray including the i-th element
int Len = 1;
// Stores largest element in
// current subarray
int Max = arr[0];
// Traverse the array
for(int i = 1; i < n; i++)
{
// If arr[i] and arr[i - 1]
// are either even numbers
// or odd numbers
if (arr[i] % 2 == arr[i - 1] % 2)
{
// Update Len
Len++;
// Update Max
if (arr[i] > Max)
Max = arr[i];
// If Len greater than
// maxLen
if (Len >= maxLen)
{
maxLen = Len;
// Update MaxElem
if (Max >= MaxElem)
MaxElem = Max;
}
}
else
{
// Update Len
Len = 1;
// Update Max
Max = arr[i];
// If Len greater
// than maxLen
if (Len >= maxLen)
{
// Update maxLen
maxLen = Len;
// If Max greater
// than MaxElem
if (Max >= MaxElem)
{
// Update MaxElem
MaxElem = Max;
}
}
}
}
return MaxElem;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 7, 8, 12, 10 };
int n = arr.length;
System.out.print(maxelementLongestSub(arr, n));
}
}
// This code is contributed by sourav singh
Python3
# Python3 program to implement # the above approach # Function to find the largest element # of the longest subarray consisting # only of odd or even elements only def maxelementLongestSub(arr, n): # Stores largest element of the # longest sub-array till i-th index MaxElem = arr[0] # Stores maximum length of the # longest sub-array till i-th index maxLen = 1 # Stores length of the current # sub-array including the i-th element Len = 1 # Stores largest element in # current sub-array Max = arr[0] for i in range(1, n): # If arr[i] and arr[i - 1] # are either even numbers # or odd numbers if arr[i] % 2 == arr[i - 1] % 2: # Update Len Len += 1 # Update Max if arr[i] > Max: Max = arr[i] # If Len greater than # maxLen if Len >= maxLen: maxLen = Len # Update MaxElem if Max >= MaxElem: MaxElem = Max else: # Update Len Len = 1 # Update Max Max = arr[i] # If Len greater # than maxLen if Len >= maxLen: maxLen = Len # If Max greater # than MaxElem if Max >= MaxElem: MaxElem = Max return MaxElem # Driver Code arr = [ 1, 3, 5, 7, 8, 12, 10 ] n = len(arr) print(maxelementLongestSub(arr, n)) # This code is contributed by sourav singh
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the largest element
// of the longest subarray consisting
// only of odd or even elements only
static int maxelementLongestSub(int[] arr,
int n)
{
// Stores largest element of the
// longest subarray till i-th index
int MaxElem = arr[0];
// Stores maximum length of the
// longest subarray till i-th index
int maxLen = 1;
// Stores length of the current
// subarray including the i-th element
int Len = 1;
// Stores largest element in
// current subarray
int Max = arr[0];
// Traverse the array
for(int i = 1; i < n; i++)
{
// If arr[i] and arr[i - 1]
// are either even numbers
// or odd numbers
if (arr[i] % 2 == arr[i - 1] % 2)
{
// Update Len
Len++;
// Update Max
if (arr[i] > Max)
Max = arr[i];
// If Len greater than
// maxLen
if (Len >= maxLen)
{
maxLen = Len;
// Update MaxElem
if (Max >= MaxElem)
MaxElem = Max;
}
}
else
{
// Update Len
Len = 1;
// Update Max
Max = arr[i];
// If Len greater
// than maxLen
if (Len >= maxLen)
{
// Update maxLen
maxLen = Len;
// If Max greater
// than MaxElem
if (Max >= MaxElem)
{
// Update MaxElem
MaxElem = Max;
}
}
}
}
return MaxElem;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 3, 5, 7, 8, 12, 10 };
int n = arr.Length;
// Function call
Console.Write(maxelementLongestSub(arr, n));
}
}
// This code is contributed by sourav singh
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the largest element
// of the longest subarray consisting
// only of odd or even elements only
function maxelementLongestSub(arr, n)
{
// Stores largest element of the
// longest subarray till i-th index
var MaxElem = arr[0];
// Stores maximum length of the
// longest subarray till i-th index
var maxLen = 1;
// Stores length of the current
// subarray including the i-th element
var Len = 1;
// Stores largest element in
// current subarray
var Max = arr[0];
// Traverse the array
for (var i = 1; i < n; i++) {
// If arr[i] and arr[i - 1]
// are either even numbers
// or odd numbers
if (arr[i] % 2 == arr[i - 1] % 2) {
// Update Len
Len++;
// Update Max
if (arr[i] > Max) Max = arr[i];
// If Len greater than
// maxLen
if (Len >= maxLen) {
maxLen = Len;
// Update MaxElem
if (Max >= MaxElem) MaxElem = Max;
}
} else {
// Update Len
Len = 1;
// Update Max
Max = arr[i];
// If Len greater
// than maxLen
if (Len >= maxLen) {
// Update maxLen
maxLen = Len;
// If Max greater
// than MaxElem
if (Max >= MaxElem) {
// Update MaxElem
MaxElem = Max;
}
}
}
}
return MaxElem;
}
// Driver Code
var arr = [1, 3, 5, 7, 8, 12, 10];
var n = arr.length;
document.write(maxelementLongestSub(arr, n));
</script>
Producción:
7
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por varuntak22 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA