Dada una array arr[] y dos enteros X e Y. La tarea es encontrar una sub-array de tamaño de al menos X y como máximo Y con el promedio máximo (promedio de los elementos de la sub-array).
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5} X = 2, Y = 3
Salida: 4.5
Podemos tomar el subarreglo {4, 5} que nos da el promedio máximo.
Entrada: arr[] = {6, 7, 8, 3, 2, 4, 2} X = 2, Y = 4
Salida: 7,5
Enfoque: iterar sobre cada subarreglo de tamaño desde X hasta el tamaño Y y encontrar el promedio máximo entre todos esos subarreglos. Podemos usar dos bucles for anidados para iterar sobre todos los subconjuntos cuyo tamaño varía de X a Y. Para reducir la complejidad del tiempo, podemos usar el conjunto de suma de prefijos para obtener la suma de cualquier subconjunto en complejidad O(1).
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 maximum average // of the sub-array with size // atleast x and atmost y double maxAvgSubArray(int a[], int n, int x, int y) { // Calculate the prefix sum array int prefix[n]; prefix[0] = a[0]; for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + a[i]; double maximum = 0; // Iterate over all sub-arrays for (int i = 0; i < n; i++) { // Sub-arrays of size X to Y for (int j = i + x - 1; j < i + y && j < n; j++) { // Get the sum of the sub-array double sum = prefix[j]; if (i > 0) sum -= prefix[i - 1]; // Find average of sub-array double current = sum / (double)(j - i + 1); // Store the maximum of average maximum = max(maximum, current); } } return maximum; } // Driver code int main() { int a[] = { 6, 7, 8, 3, 2, 4, 2 }; int X = 2, Y = 4; int n = sizeof(a) / sizeof(a[0]); cout << maxAvgSubArray(a, n, X, Y); return 0; }
Java
// Java implementation of the approach class GfG { // Function to return the maximum average // of the sub-array with size // atleast x and atmost y static double maxAvgSubArray(int a[], int n, int x, int y) { // Calculate the prefix sum array int prefix[] = new int[n]; prefix[0] = a[0]; for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + a[i]; double maximum = 0; // Iterate over all sub-arrays for (int i = 0; i < n; i++) { // Sub-arrays of size X to Y for (int j = i + x - 1; j < i + y && j < n; j++) { // Get the sum of the sub-array double sum = prefix[j]; if (i > 0) sum -= prefix[i - 1]; // Find average of sub-array double current = sum / (double)(j - i + 1); // Store the maximum of average maximum = Math.max(maximum, current); } } return maximum; } // Driver code public static void main(String[] args) { int a[] = { 6, 7, 8, 3, 2, 4, 2 }; int X = 2, Y = 4; int n = a.length; System.out.println(maxAvgSubArray(a, n, X, Y)); } }
Python3
# Python3 implementation of the approach # Function to return the maximum average # of the sub-array with size # atleast x and atmost y def maxAvgSubArray(a, n, x, y) : # Calculate the prefix sum array prefix = [0] * n ; prefix[0] = a[0]; for i in range(1, n) : prefix[i] = prefix[i - 1] + a[i]; maximum = 0; # Iterate over all sub-arrays for i in range(n) : j = i + x - 1 # Sub-arrays of size X to Y while(j < i + y and j < n) : # Get the sum of the sub-array sum = prefix[j]; if (i > 0) : sum -= prefix[i - 1]; # Find average of sub-array current = sum / (j - i + 1); # Store the maximum of average maximum = max(maximum, current); j += 1 return maximum; # Driver code if __name__ == "__main__" : a = [ 6, 7, 8, 3, 2, 4, 2 ]; X = 2; Y = 4; n = len(a); print(maxAvgSubArray(a, n, X, Y)); # This code is contributed by Ryuga
C#
// C# implementation of the approach using System; class GFG { // Function to return the maximum // average of the sub-array with // size atleast x and atmost y public static double maxAvgSubArray(int[] a, int n, int x, int y) { // Calculate the prefix sum array int[] prefix = new int[n]; prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; } double maximum = 0; // Iterate over all sub-arrays for (int i = 0; i < n; i++) { // Sub-arrays of size X to Y for (int j = i + x - 1; j < i + y && j < n; j++) { // Get the sum of the sub-array double sum = prefix[j]; if (i > 0) { sum -= prefix[i - 1]; } // Find average of sub-array double current = sum / (double)(j - i + 1); // Store the maximum of average maximum = Math.Max(maximum, current); } } return maximum; } // Driver code public static void Main(string[] args) { int[] a = new int[] {6, 7, 8, 3, 2, 4, 2}; int X = 2, Y = 4; int n = a.Length; Console.WriteLine(maxAvgSubArray(a, n, X, Y)); } } // This code is contributed by Shrikant13
PHP
<?php // PHP implementation of the approach // Function to return the maximum average // of the sub-array with size // atleast x and atmost y function maxAvgSubArray($a, $n, $x, $y) { // Calculate the prefix sum array $prefix = array(); $prefix[0] = $a[0]; for ($i = 1; $i < $n; $i++) $prefix[$i] = $prefix[$i - 1] + $a[$i]; $maximum = 0; // Iterate over all sub-arrays for ($i = 0; $i < $n; $i++) { // Sub-arrays of size X to Y for ($j = $i + $x - 1; $j < $i + $y && $j < $n; $j++) { // Get the sum of the sub-array $sum = $prefix[$j]; if ($i > 0) $sum -= $prefix[$i - 1]; // Find average of sub-array $current = ($sum / ($j - $i + 1)); // Store the maximum of average $maximum = max($maximum, $current); } } return $maximum; } // Driver code $a = array(6, 7, 8, 3, 2, 4, 2); $X = 2; $Y = 4; $n = sizeof($a); echo maxAvgSubArray($a, $n, $X, $Y); // This code is contributed by Akanksha Rai ?>
Javascript
<script> // javascript program for the above approach // Function to return the maximum average // of the sub-array with size // atleast x and atmost y function maxAvgSubArray(a, n, x, y) { // Calculate the prefix sum array let prefix = new Array(n).fill(0); prefix[0] = a[0]; for (let i = 1; i < n; i++) prefix[i] = prefix[i - 1] + a[i]; let maximum = 0; // Iterate over all sub-arrays for (let i = 0; i < n; i++) { // Sub-arrays of size X to Y for (let j = i + x - 1; j < i + y && j < n; j++) { // Get the sum of the sub-array let sum = prefix[j]; if (i > 0) sum -= prefix[i - 1]; // Find average of sub-array let current = sum / (j - i + 1); // Store the maximum of average maximum = Math.max(maximum, current); } } return maximum; } // Driver Code let a = [ 6, 7, 8, 3, 2, 4, 2 ]; let X = 2, Y = 4; let n = a.length; document.write(maxAvgSubArray(a, n, X, Y)); </script>
7.5
Complejidad temporal: O(N * (YX))
Espacio auxiliar: O(N)