Dada una array arr[] de n enteros. La tarea es encontrar la longitud máxima del subarreglo que tiene el valor promedio máximo (promedio de los elementos del subarreglo).
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
Ejemplos:
Entrada: arr[] = {2, 3, 4, 5, 6}
Salida: 1
{6} es el subarreglo requerido
Entrada: arr[] = {6, 1, 6, 6, 0}
Salida: 2
{ 6} y {6, 6} son los subconjuntos con valor promedio máximo.
Acercarse:
- El promedio de cualquier subarreglo no puede exceder el valor máximo del arreglo.
- El valor máximo posible del promedio será el elemento máximo de la array.
- Entonces, para encontrar la subarray de longitud máxima con el valor promedio máximo, tenemos que encontrar la longitud máxima de la subarray donde cada elemento de la subarray es igual e igual al elemento máximo de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the max length of the
// sub-array that have the maximum average
// (average value of the elements)
int maxLenSubArr(int a[], int n)
{
int count, j;
int cm = 1, max = 0;
// Finding the maximum value
for (int i = 0; i < n; i++) {
if (a[i] > max)
max = a[i];
}
for (int i = 0; i < n - 1;) {
count = 1;
// If consecutive maximum found
if (a[i] == a[i + 1] && a[i] == max) {
// Find the max length of consecutive max
for (j = i + 1; j < n; j++) {
if (a[j] == max) {
count++;
i++;
}
else
break;
}
if (count > cm)
cm = count;
}
else
i++;
}
return cm;
}
// Driver code
int main()
{
int arr[] = { 6, 1, 6, 6, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxLenSubArr(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the max length of the
// sub-array that have the maximum average
// (average value of the elements)
static int maxLenSubArr(int a[], int n)
{
int count, j;
int cm = 1, max = 0;
// Finding the maximum value
for (int i = 0; i < n; i++)
{
if (a[i] > max)
max = a[i];
}
for (int i = 0; i < n - 1; )
{
count = 1;
// If consecutive maximum found
if (a[i] == a[i + 1] && a[i] == max)
{
// Find the max length of consecutive max
for (j = i + 1; j < n; j++)
{
if (a[j] == max)
{
count++;
i++;
}
else
break;
}
if (count > cm)
cm = count;
}
else
i++;
}
return cm;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 6, 1, 6, 6, 0 };
int n = arr.length;
System.out.println(maxLenSubArr(arr, n));
}
}
// This code is contributed by Code_Mech.
Python3
# Python3 implementation of the approach # Function to return the max length of the # sub-array that have the maximum average # (average value of the elements) def maxLenSubArr(a, n): cm, Max = 1, 0 # Finding the maximum value for i in range(0, n): if a[i] > Max: Max = a[i] i = 0 while i < n - 1: count = 1 # If consecutive maximum found if a[i] == a[i + 1] and a[i] == Max: # Find the max length of # consecutive max for j in range(i + 1, n): if a[j] == Max: count += 1 i += 1 else: break if count > cm: cm = count else: i += 1 i += 1 return cm # Driver code if __name__ == "__main__": arr = [6, 1, 6, 6, 0] n = len(arr) print(maxLenSubArr(arr, n)) # This code is contributed by # Rituraj Jain
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the max length of the
// sub-array that have the maximum average
// (average value of the elements)
static int maxLenSubArr(int []a, int n)
{
int count, j;
int cm = 1, max = 0;
// Finding the maximum value
for (int i = 0; i < n; i++)
{
if (a[i] > max)
max = a[i];
}
for (int i = 0; i < n - 1; )
{
count = 1;
// If consecutive maximum found
if (a[i] == a[i + 1] && a[i] == max)
{
// Find the max length of consecutive max
for (j = i + 1; j < n; j++)
{
if (a[j] == max)
{
count++;
i++;
}
else
break;
}
if (count > cm)
cm = count;
}
else
i++;
}
return cm;
}
// Driver code
static public void Main ()
{
int []arr = { 6, 1, 6, 6, 0 };
int n = arr.Length;
Console.WriteLine(maxLenSubArr(arr, n));
}
}
// This code is contributed by ajit.
PHP
<?php
// PHP implementation of the approach
// Function to return the max length of the
// sub-array that have the maximum average
// (average value of the elements)
function maxLenSubArr($a, $n)
{
$cm = 1 ;
$max = 0;
// Finding the maximum value
for ($i = 0; $i < $n; $i++)
{
if ($a[$i] > $max)
$max = $a[$i];
}
for ($i = 0; $i < $n - 1;)
{
$count = 1;
// If consecutive maximum found
if ($a[$i] == $a[$i + 1] &&
$a[$i] == $max)
{
// Find the max length of
// consecutive max
for ($j = $i + 1; $j < $n; $j++)
{
if ($a[$j] == $max)
{
$count++;
$i++;
}
else
break;
}
if ($count > $cm)
$cm = $count;
}
else
$i++;
}
return $cm;
}
// Driver code
$arr = array( 6, 1, 6, 6, 0 );
$n = sizeof($arr);
echo maxLenSubArr($arr, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the max length of the
// sub-array that have the maximum average
// (average value of the elements)
function maxLenSubArr(a, n)
{
let count, j;
let cm = 1, max = 0;
// Finding the maximum value
for (let i = 0; i < n; i++)
{
if (a[i] > max)
max = a[i];
}
for (let i = 0; i < n - 1; )
{
count = 1;
// If consecutive maximum found
if (a[i] == a[i + 1] && a[i] == max)
{
// Find the max length of consecutive max
for (j = i + 1; j < n; j++)
{
if (a[j] == max)
{
count++;
i++;
}
else
break;
}
if (count > cm)
cm = count;
}
else
i++;
}
return cm;
}
let arr = [ 6, 1, 6, 6, 0 ];
let n = arr.length;
document.write(maxLenSubArr(arr, n));
</script>
Producción:
2
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por SURENDRA_GANGWAR y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA