查找 k 個長度的最大平均子數組 · GeeksForGeeks 中文系列教程

# 查找 k 個長度的最大平均子數組 > 原文： [https://www.geeksforgeeks.org/find-maximum-average-subarray-of-k-length/](https://www.geeksforgeeks.org/find-maximum-average-subarray-of-k-length/) 給定具有正數和負數的數組，請找到給定長度的最大平均子數組。例： ``` 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 ``` 一個**簡單解決方案**是運行兩個循環。外循環選擇起始點，內循環從起始點開始直到長度“ k”，然后計算元素的平均值。該解決方案的時間復雜度為 O（n * k）。 **更好的解決方案**是創建大小為 n 的輔助數組。將元素的累積和存儲在此數組中。令數組為 csum []。 csum [i]存儲從 arr [0]到 arr [i]的元素之和。一旦有了 csum []數組，就可以在`O(1)`時間中計算兩個索引之間的和。以下是此想法的實現。一個觀察是，給定長度的子數組如果具有最大和，則具有最大平均值。因此我們可以通過比較和來避免浮點運算。 ## CPP ``` // 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 // 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\. ``` ## C# ```cs // 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\. ``` ## Python3 ```py # 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 ``` ## PHP ```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\. ?> ``` Output: ``` 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）對 i 從'k'到'n-1'的每個元素 arr [i]執行以下操作 …….a）從 sum 中刪除 arr [ik] 并添加 arr [i]，即求和+ = arr [i] – arr [ik] …….b）如果到目前為止新的總和大于 max_sum，則更新 max_sum。 3）返回“ max_sum” ## CPP ``` // 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 // 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 ```py # 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 // 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\. ?> ``` 輸出： ``` The maximum average subarray of length 4 begins at index 1 ``` 該方法的時間復雜度也是`O(n)`，但是它需要恒定的額外空間。