मान लीजिए हमारे पास n पूर्णांकों वाली एक सरणी है, हमें उस सन्निहित सबअरे को ढूंढना है जिसकी लंबाई k से अधिक या बराबर है और जिसका औसत मान अधिकतम है। हमें अधिकतम औसत मान वापस करना है।
इसलिए, यदि इनपुट [1,12,-5,-6,50,3] जैसा है, k = 4, तो आउटपुट 12.75 होगा, क्योंकि जब लंबाई 5 है, तो अधिकतम औसत मान 10.8 है, जब लंबाई 6 है, तो अधिकतम औसत मान 9.16667 है। इस प्रकार आउटपुट 12.75 है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- एक फ़ंक्शन
ok()परिभाषित करें, जोx, सरणीnums,kलेगा n := nums का आकार- आकार
nकी एक सरणीarrपरिभाषित करें i := 0सेn-1तक लूप चलाएं:arr[i] := nums[i] - x
sum := 0, last := 0i := 0सेk-1तक लूप चलाएं:sum := sum + arr[i]
- यदि
sum >= 0, तोtrueवापस करें i := 0, j := kसे शुरू करकेj < nतक लूप चलाएं:last := last + arr[i]sum := sum + arr[j]- यदि
last < 0, तो:sum := sum - lastlast := 0
- यदि
sum >= 0, तोtrueवापस करें
falseवापस करें- मुख्य विधि से निम्नलिखित करें:
ret := 0, low := -inf, high := infhigh - low > 10^-5होने तक लूप चलाएं:mid := low + (high - low) / 2- यदि
ok(mid, nums, k)सत्य है, तो:low := midret := mid
- अन्यथा:
high := mid
retवापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(double x, vector <int>& nums, int k){
int n = nums.size();
double arr[n];
for (int i = 0; i < n; i++) {
arr[i] = nums[i] - x;
}
double sum = 0;
double last = 0;
for (int i = 0; i < k; i++) {
sum += arr[i];
}
if (sum >= 0)
return true;
for (int i = 0, j = k; j < n; i++, j++) {
last += arr[i];
sum += arr[j];
if (last < 0) {
sum -= last;
last = 0;
}
if (sum >= 0)
return true;
}
return false;
}
double findMaxAverage(vector<int>& nums, int k) {
double ret = 0;
double low = INT_MIN;
double high = INT_MAX;
while (high - low > 1e-5) {
double mid = low + (high - low) / 2;
if (ok(mid, nums, k)) {
low = mid;
ret = mid;
} else {
high = mid;
}
}
return ret;
}
};
int main(){
Solution ob;
vector<int> v = {1,12,-5,-6,50,3};
cout << (ob.findMaxAverage(v, 4));
}
इनपुट
{1,12,-5,-6,50,3},4
आउटपुट
12.75000