给定一个正数和负数的数组，求给定长度的最大平均子数组。
null
例子：
Input: arr[] = {1, 12, -5, -6, 50, 3}, k = 4Output: Maximum average subarray of length 4 begins at index 1.Maximum average is (12 - 5 - 6 + 50)/4 = 51/4
A. 简单解决方案 就是运行两个循环。外循环选择起点，内循环从起点到长度“k”，并计算元素的平均值。该解的时间复杂度为O（n*k）。
A. 更好的解决方案 是创建一个大小为n的辅助数组。在该数组中存储元素的累积和。让数组为csum[]。csum[i]存储从arr[0]到arr[i]的元素之和。一旦我们有了csum[]数组，我们就可以在O（1）时间内计算两个索引之间的和。 下面是这个想法的实施。一个观察结果是，给定长度的子阵列如果有最大和，则具有最大平均值。所以我们可以通过比较和来避免浮点运算。
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> |
输出：
The maximum average subarray of length 4 begins at index 1
上述解的时间复杂度为O（n），但需要O（n）辅助空间。 我们可以使用下面的方法来避免额外的空间需求 有效方法 . 1） 计算第一个“k”元素的和，即元素arr[0..k-1]。让这个总和成为“总和”。将“max_sum”初始化为“sum” 2） 对每个元素arr[i]执行以下操作，其中i从“k”到“n-1”变化 …….a） 从总和中删除arr[i-k]并加上arr[i]，即do sum+=arr[i]–arr[i-k] …….b） 如果到目前为止新的总和超过最大总和，请更新最大总和。 3） 返回“最大值”
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++) { int 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> |
输出：
The maximum average subarray of length 4 begins at index 1
这种方法的时间复杂度也是O（n），但它需要恒定的额外空间。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
