C++でkの長さの最大平均サブ配列を見つける

この問題では、正と負の値と整数kで構成されるサイズnの配列arr[]が与えられます。私たちのタスクは、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