C++-এ নির্দিষ্ট দৈর্ঘ্যের সাবঅ্যারের সর্বাধিক গড় বের করুন

একটি অ্যারে (পজিটিভ ও নেগেটিভ মান) এবং একটি পূর্ণসংখ্যা k দেওয়া আছে। দৈর্ঘ্য k এর সাবঅ্যারেগুলোর মধ্যে যেটির গড় (অর্থাৎ যোগফল) সর্বাধিক, সেই সাবঅ্যারের শুরুতেই ইনডেক্স বের করুন।

উদাহরণ

ইনপুট: arr = {4,-1,5,6,-2,4}, k = 3

আউটপুট: 1 (সাবঅ্যারে {-1,5,6} ইনডেক্স ১ থেকে শুরু, যোগফল ১০)

অ্যালগরিদম: প্রিফিক্স সম + স্লাইডিং উইন্ডো

1. auxSum[i] = arr[0] থেকে arr[i] পর্যন্ত কামুলেটিভ সম।
2. সাবঅ্যারে [i..j] এর সম = auxSum[j] - auxSum[i-1]।
3. দৈর্ঘ্য k হলে: sum = auxSum[i] - auxSum[i-k]।
4. সব উইন্ডোর সম চেক করে ম্যাক্সিমাম বের করুন।

C++ প্রোগ্রাম

#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

উন্নতি: O(1) স্পেস (স্লাইডিং উইন্ডো)

int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum, startIdx = 0;
for (int i = k; i < n; i++) {
    windowSum += arr[i] - arr[i-k];
    if (windowSum > maxSum) {
        maxSum = windowSum;
        startIdx = i - k + 1;
    }
}
// auxSumArray লাগে না, স্পেস O(1)

কমপ্লেক্সিটি

স্লাইডিং উইন্ডো পদ্ধতিই প্রিয়।