C++ में k लंबाई की अधिकतम औसत उप-सरणी ज्ञात कीजिए

इस समस्या में, हमें आकार n का एक सरणी arr[] दिया जाता है जिसमें धनात्मक और ऋणात्मक मान और एक पूर्णांक k होता है। हमारा कार्य k लंबाई की अधिकतम औसत उप-सरणी खोजना है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट: गिरफ्तारी [] ={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