C++ में कम से कम X और अधिकतम Y आकार के सबएरे का अधिकतम औसत

समस्या कथन

एक ऐरे arr[] और दो पूर्णांक X और Y दिए गए हैं। कार्य कम से कम X और अधिकतम Y आकार के सब-एरे को ढूंढना है जिसका औसत अधिकतम हो।

उदाहरण

यदि इनपुट ऐरे है {2, 10, 15, 7, 8, 4} और x = 3 और Y = 3 तो हम अधिकतम औसत 12.5 निम्नानुसार प्राप्त कर सकते हैं:

(10 + 15) / 2 = 12.5

एल्गोरिदम

• X से Y आकार तक के हर सब-एरे पर पुनरावृति करें और सभी ऐसे सब-एरे में अधिकतम औसत ढूंढें।
• समय जटिलता कम करने के लिए, हम किसी भी सब-एरे का योग O(1) जटिलता में प्राप्त करने के लिए प्रीफिक्स सम ऐरे का उपयोग कर सकते हैं।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

double getMaxAverage(int* arr, int n, int x, int y) {
    int prefix[n];
    prefix[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
    double maxAverage = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + x - 1; j < i + y && j < n; ++j) {
            double sum = prefix[j];
            if (i > 0) {
                sum = sum - prefix[i - 1];
                double current = sum / double(j - i + 1);
                maxAverage = max(maxAverage, current);
            }
        }
    }
    return maxAverage;
}

int main() {
    int arr[] = {2, 10, 15, 7, 8, 4};
    int x = 2;
    int y = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum average = " << getMaxAverage(arr, n, x, y) << endl;
    return 0;
}

आउटपुट

Maximum average = 12.5