在C ++中找到k长度的最大平均子数组

  • Z时代
  • 2024-01-10
  • 分类：综合

在这个问题中，我们得到一个大小为n的数组arr []，该数组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<<"长度的最大平均子数组 "<<k<<" begins at index "<<findMaxSubArrayAverage(arr, n, k);
   return 0;
}
输出结果
长度的最大平均子数组 3 begins at index 1

以上是 在C ++中找到k长度的最大平均子数组 的全部内容， 来源链接： utcz.com/z/320064.html

回到顶部