समस्या कथन
एक सरणी गिरफ्तारी [] और दो पूर्णांक 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
