Dada una array con números positivos y negativos, encuentre el subarreglo promedio máximo de la longitud dada.
Ejemplo:
Input: arr[] = {1, 12, -5, -6, 50, 3}, k = 4
Output: Maximum average subarray of length 4 begins
at index 1.
Maximum average is (12 - 5 - 6 + 50)/4 = 51/4
Una solución simple es ejecutar dos bucles. El ciclo externo elige el punto de inicio y el ciclo interno va a la longitud ‘k’ desde el punto de inicio y calcula el promedio de los elementos.
Complejidad de tiempo: O(n*k), ya que estamos usando bucles anidados para recorrer n*k veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Una mejor solución es crear una array auxiliar de tamaño n. Almacene la suma acumulativa de elementos en esta array. Sea la array csum[]. csum[i] almacena la suma de elementos de arr[0] a arr[i]. Una vez que tenemos la array csum[] con nosotros, podemos calcular la suma entre dos índices en tiempo O(1).
A continuación se muestra la implementación de esta idea. Una observación es que un subarreglo de una longitud dada tiene un promedio máximo si tiene una suma máxima. Entonces podemos evitar la aritmética de coma flotante simplemente comparando sumas.
C++
// C++ program to find maximum average subarray
// of given length.
#include<bits/stdc++.h>
using namespace std;
// Returns beginning index of maximum average
// subarray of length 'k'
int findMaxAverage(int arr[], int n, int k)
{
// Check if 'k' is valid
if (k > n)
return -1;
// Create and fill array to store cumulative
// sum. csum[i] stores sum of arr[0] to arr[i]
int *csum = new int[n];
csum[0] = arr[0];
for (int i=1; i<n; i++)
csum[i] = csum[i-1] + arr[i];
// Initialize max_sm as sum of first subarray
int max_sum = csum[k-1], max_end = k-1;
// Find sum of other subarrays and update
// max_sum if required.
for (int i=k; i<n; i++)
{
int curr_sum = csum[i] - csum[i-k];
if (curr_sum > max_sum)
{
max_sum = curr_sum;
max_end = i;
}
}
delete [] csum; // To avoid memory leak
// Return starting index
return max_end - k + 1;
}
// Driver program
int main()
{
int arr[] = {1, 12, -5, -6, 50, 3};
int k = 4;
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum average subarray of "
"length "<< k << " begins at index "
<< findMaxAverage(arr, n, k);
return 0;
}
Java
// Java program to find maximum average
// subarray of given length.
import java .io.*;
class GFG {
// Returns beginning index
// of maximum average
// subarray of length 'k'
static int findMaxAverage(int []arr,
int n, int k)
{
// Check if 'k' is valid
if (k > n)
return -1;
// Create and fill array
// to store cumulative
// sum. csum[i] stores
// sum of arr[0] to arr[i]
int []csum = new int[n];
csum[0] = arr[0];
for (int i = 1; i < n; i++)
csum[i] = csum[i - 1] + arr[i];
// Initialize max_sm as
// sum of first subarray
int max_sum = csum[k - 1],
max_end = k - 1;
// Find sum of other
// subarrays and update
// max_sum if required.
for (int i = k; i < n; i++)
{
int curr_sum = csum[i] -
csum[i - k];
if (curr_sum > max_sum)
{
max_sum = curr_sum;
max_end = i;
}
}
// To avoid memory leak
//delete [] csum;
// Return starting index
return max_end - k + 1;
}
// Driver Code
static public void main (String[] args)
{
int []arr = {1, 12, -5, -6, 50, 3};
int k = 4;
int n = arr.length;
System.out.println("The maximum "
+ "average subarray of length "
+ k + " begins at index "
+ findMaxAverage(arr, n, k));
}
}
// This code is contributed by anuj_67.
Python3
# Python program to find maximum average subarray
# of given length.
# Returns beginning index of maximum average
# subarray of length 'k'
def findMaxAverage(arr, n, k):
# Check if 'k' is valid
if k > n:
return -1
# Create and fill array to store cumulative
# sum. csum[i] stores sum of arr[0] to arr[i]
csum = [0]*n
csum[0] = arr[0]
for i in range(1, n):
csum[i] = csum[i-1] + arr[i];
# Initialize max_sm as sum of first subarray
max_sum = csum[k-1]
max_end = k-1
# Find sum of other subarrays and update
# max_sum if required.
for i in range(k, n):
curr_sum = csum[i] - csum[i-k]
if curr_sum > max_sum:
max_sum = curr_sum
max_end = i
# Return starting index
return max_end - k + 1
# Driver program
arr = [1, 12, -5, -6, 50, 3]
k = 4
n = len(arr)
print("The maximum average subarray of length",k,
"begins at index",findMaxAverage(arr, n, k))
#This code is contributed by
#Smitha Dinesh Semwal
C#
// C# program to find maximum average
// subarray of given length.
using System;
class GFG{
// Returns beginning index
// of maximum average
// subarray of length 'k'
static int findMaxAverage(int []arr,
int n, int k)
{
// Check if 'k' is valid
if (k > n)
return -1;
// Create and fill array
// to store cumulative
// sum. csum[i] stores
// sum of arr[0] to arr[i]
int []csum = new int[n];
csum[0] = arr[0];
for (int i = 1; i < n; i++)
csum[i] = csum[i - 1] + arr[i];
// Initialize max_sm as
// sum of first subarray
int max_sum = csum[k - 1],
max_end = k - 1;
// Find sum of other
// subarrays and update
// max_sum if required.
for (int i = k; i < n; i++)
{
int curr_sum = csum[i] -
csum[i - k];
if (curr_sum > max_sum)
{
max_sum = curr_sum;
max_end = i;
}
}
// To avoid memory leak
//delete [] csum;
// Return starting index
return max_end - k + 1;
}
// Driver Code
static public void Main ()
{
int []arr = {1, 12, -5, -6, 50, 3};
int k = 4;
int n = arr.Length;
Console.WriteLine("The maximum average subarray of "+
"length "+ k + " begins at index "
+ findMaxAverage(arr, n, k));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find maximum
// average subarray of given length.
// Returns beginning index of
// maximum average subarray of
// length 'k'
function findMaxAverage($arr, $n, $k)
{
// Check if 'k' is valid
if ($k > $n)
return -1;
// Create and fill array to
// store cumulative sum.
// csum[i] stores sum of
// arr[0] to arr[i]
$csum = array();
$csum[0] = $arr[0];
for($i = 1; $i < $n; $i++)
$csum[$i] = $csum[$i - 1] +
$arr[$i];
// Initialize max_sm as sum
// of first subarray
$max_sum = $csum[$k - 1];
$max_end = $k - 1;
// Find sum of other subarrays
// and update max_sum if required.
for($i = $k; $i < $n; $i++)
{
$curr_sum = $csum[$i] -
$csum[$i - $k];
if ($curr_sum > $max_sum)
{
$max_sum = $curr_sum;
$max_end = $i;
}
}
// Return starting index
return $max_end - $k + 1;
}
// Driver Code
$arr = array(1, 12, -5, -6, 50, 3);
$k = 4;
$n = count($arr);
echo "The maximum average subarray of "
,"length ", $k , " begins at index "
, findMaxAverage($arr, $n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find maximum average
// subarray of given length.
// Returns beginning index
// of maximum average
// subarray of length 'k'
function findMaxAverage(arr, n, k)
{
// Check if 'k' is valid
if (k > n)
return -1;
// Create and fill array
// to store cumulative
// sum. csum[i] stores
// sum of arr[0] to arr[i]
let csum = new Array(n);
csum[0] = arr[0];
for(let i = 1; i < n; i++)
csum[i] = csum[i - 1] + arr[i];
// Initialize max_sm as
// sum of first subarray
let max_sum = csum[k - 1],
max_end = k - 1;
// Find sum of other
// subarrays and update
// max_sum if required.
for(let i = k; i < n; i++)
{
let curr_sum = csum[i] - csum[i - k];
if (curr_sum > max_sum)
{
max_sum = curr_sum;
max_end = i;
}
}
// To avoid memory leak
//delete [] csum;
// Return starting index
return max_end - k + 1;
}
// Driver code
let arr = [ 1, 12, -5, -6, 50, 3 ];
let k = 4;
let n = arr.length;
document.write("The maximum average subarray of "+
"length "+ k + " begins at index " +
findMaxAverage(arr, n, k));
// This code is contributed by divyeshrabadiya07
</script>
Producción
The maximum average subarray of length 4 begins at index 1
Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es el número de elementos de la array.
Espacio auxiliar: O(n), ya que estamos usando espacio extra para la array csum.
Podemos evitar la necesidad de espacio extra usando el Método Eficiente a continuación .
- Calcule la suma de los primeros elementos ‘k’, es decir, los elementos arr[0..k-1]. Sea esta suma ‘suma’. Inicialice ‘max_sum’ como ‘sum’
- Haga lo siguiente para cada elemento arr[i] donde i varía de ‘k’ a ‘n-1’
- Elimine arr[ik] de sum y agregue arr[i], es decir, haga sum += arr[i] – arr[ik]
- Si la nueva suma es mayor que max_sum hasta ahora, actualice max_sum.
- Devuelve ‘max_sum’
C++
// C++ program to find maximum average subarray
// of given length.
#include<bits/stdc++.h>
using namespace std;
// Returns beginning index of maximum average
// subarray of length 'k'
int findMaxAverage(int arr[], int n, int k)
{
// Check if 'k' is valid
if (k > n)
return -1;
// Compute sum of first 'k' elements
int sum = arr[0];
for (int i=1; i<k; i++)
sum += arr[i];
int max_sum = sum, max_end = k-1;
// Compute sum of remaining subarrays
for (int i=k; i<n; i++)
{
sum = sum + arr[i] - arr[i-k];
if (sum > max_sum)
{
max_sum = sum;
max_end = i;
}
}
// Return starting index
return max_end - k + 1;
}
// Driver program
int main()
{
int arr[] = {1, 12, -5, -6, 50, 3};
int k = 4;
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum average subarray of "
"length "<< k << " begins at index "
<< findMaxAverage(arr, n, k);
return 0;
}
Java
// Java program to find maximum average subarray
// of given length.
import java.io.*;
class GFG {
// Returns beginning index of maximum average
// subarray of length 'k'
static int findMaxAverage(int arr[], int n, int k)
{
// Check if 'k' is valid
if (k > n)
return -1;
// Compute sum of first 'k' elements
int sum = arr[0];
for (int i = 1; i < k; i++)
sum += arr[i];
int max_sum = sum, max_end = k-1;
// Compute sum of remaining subarrays
for (int i = k; i < n; i++)
{
sum = sum + arr[i] - arr[i-k];
if (sum > max_sum)
{
max_sum = sum;
max_end = i;
}
}
// Return starting index
return max_end - k + 1;
}
// Driver program
public static void main (String[] args)
{
int arr[] = {1, 12, -5, -6, 50, 3};
int k = 4;
int n = arr.length;
System.out.println( "The maximum average"
+ " subarray of length " + k
+ " begins at index "
+ findMaxAverage(arr, n, k));
}
}
// This code is contributed by anuj_67.
Python3
# Python 3 program to find maximum
# average subarray of given length.
# Returns beginning index of maximum
# average subarray of length 'k'
def findMaxAverage(arr, n, k):
# Check if 'k' is valid
if (k > n):
return -1
# Compute sum of first 'k' elements
sum = arr[0]
for i in range(1, k):
sum += arr[i]
max_sum = sum
max_end = k - 1
# Compute sum of remaining subarrays
for i in range(k, n):
sum = sum + arr[i] - arr[i - k]
if (sum > max_sum):
max_sum = sum
max_end = i
# Return starting index
return max_end - k + 1
# Driver program
arr = [1, 12, -5, -6, 50, 3]
k = 4
n = len(arr)
print("The maximum average subarray of length", k,
"begins at index",
findMaxAverage(arr, n, k))
# This code is contributed by
# Smitha Dinesh Semwal
C#
// C# program to find maximum average
// subarray of given length.
using System;
class GFG {
// Returns beginning index of
// maximum average subarray of
// length 'k'
static int findMaxAverage(int []arr,
int n, int k)
{
// Check if 'k' is valid
if (k > n)
return -1;
// Compute sum of first 'k'
// elements
int sum = arr[0];
for (int i = 1; i < k; i++)
sum += arr[i];
int max_sum = sum;
int max_end = k-1;
// Compute sum of remaining
// subarrays
for (int i = k; i < n; i++)
{
sum = sum + arr[i] - arr[i-k];
if (sum > max_sum)
{
max_sum = sum;
max_end = i;
}
}
// Return starting index
return max_end - k + 1;
}
// Driver program
public static void Main ()
{
int []arr = {1, 12, -5, -6, 50, 3};
int k = 4;
int n = arr.Length;
Console.WriteLine( "The maximum "
+ "average subarray of length "
+ k + " begins at index "
+ findMaxAverage(arr, n, k));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find maximum
// average subarray of given length.
// Returns beginning index
// of maximum average
// subarray of length 'k'
function findMaxAverage($arr, $n, $k)
{
// Check if 'k' is valid
if ($k > $n)
return -1;
// Compute sum of first
// 'k' elements
$sum = $arr[0];
for($i = 1; $i < $k; $i++)
$sum += $arr[$i];
$max_sum = $sum;
$max_end = $k-1;
// Compute sum of
// remaining subarrays
for($i = $k; $i < $n; $i++)
{
$sum = $sum + $arr[$i] -
$arr[$i - $k];
if ($sum > $max_sum)
{
$max_sum = $sum;
$max_end = $i;
}
}
// Return starting index
return $max_end - $k + 1;
}
// Driver Code
$arr = array(1, 12, -5, -6, 50, 3);
$k = 4;
$n = count($arr);
echo "The maximum average subarray of ",
"length ", $k , " begins at index "
, findMaxAverage($arr, $n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find maximum average
// subarray of given length.
// Returns beginning index of
// maximum average subarray of
// length 'k'
function findMaxAverage(arr, n, k)
{
// Check if 'k' is valid
if (k > n)
return -1;
// Compute sum of first 'k'
// elements
let sum = arr[0];
for (let i = 1; i < k; i++)
sum += arr[i];
let max_sum = sum;
let max_end = k-1;
// Compute sum of remaining
// subarrays
for (let i = k; i < n; i++)
{
sum = sum + arr[i] - arr[i-k];
if (sum > max_sum)
{
max_sum = sum;
max_end = i;
}
}
// Return starting index
return max_end - k + 1;
}
let arr = [1, 12, -5, -6, 50, 3];
let k = 4;
let n = arr.length;
document.write( "The maximum "
+ "average subarray of length "
+ k + " begins at index "
+ findMaxAverage(arr, n, k));
// This code is contributed by suresh07.
</script>
Producción
The maximum average subarray of length 4 begins at index 1
Complejidad de tiempo : O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es el número de elementos de la array.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA