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