資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在 C++ 中找出最大長度為 k 的平均子陣列
在這個問題中，我們給定一個大小為 n 的陣列 arr[]，其中包含正值和負值，以及一個整數 k。我們的任務是找到長度為 k 的最大平均子陣列。
讓我們舉個例子來理解這個問題，
輸入：arr[] = {4, -1, 5, 6, -2, 4} k = 3
輸出：10
說明：
大小為 3 的子陣列中最大和為 -1、5、6 = 10
解決方案方法
這個問題的解決方案是使用一個輔助陣列來儲存陣列中到當前索引為止的累積和。
要找出子陣列的和，我們需要計算子陣列位置索引之間的差值。
程式說明我們解決方案的工作原理：
示例
#include<bits/stdc++.h>
using namespace std;
int findMaxSubArrayAverage(int arr[], int n, int k) {
if (k > n)
return -1;
int *auxSumArray = new int[n];
auxSumArray[0] = arr[0];
for (int i=1; i<n; i++)
auxSumArray[i] = auxSumArray[i-1] + arr[i];
int maxSum = auxSumArray[k-1], subEndIndex = k-1;
for (int i=k; i<n; i++) {
int sumVal = auxSumArray[i] - auxSumArray[i-k];
if (sumVal > maxSum) {
maxSum = sumVal;
subEndIndex = i;
}
}
return subEndIndex - k + 1;
}
int main() {
int arr[] = {4, -1, 5, 6, -2, 4};
int k = 3;
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum average subarray of length "<<k<<" begins at index "<<findMaxSubArrayAverage(arr, n, k);
return 0;
}輸出
The maximum average subarray of length 3 begins at index 1
更新日期：2021 年 1 月 25 日
108 次瀏覽
廣告