C++ में अधिकतम औसत सबरे II

मान लीजिए कि हमारे पास n पूर्णांकों के साथ एक सरणी है, हमें उस सन्निहित उप-सरणी को खोजना है जिसकी लंबाई k से अधिक या उसके बराबर है जिसका अधिकतम औसत मान है। हमें अधिकतम औसत मूल्य ज्ञात करना है।

इसलिए, यदि इनपुट [1,12,-5,-6,50,3], k =4 जैसा है, तो आउटपुट 12.75 होगा, क्योंकि जब लंबाई 5 होती है, तो अधिकतम औसत मान 10.8 होता है, जब लंबाई 6 होती है। , अधिकतम औसत मूल्य 9.16667 है। इस प्रकार आउटपुट 12.75 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें ठीक (), यह x, एक सरणी संख्या, k,

  लेगा

• n :=अंकों का आकार

• आकार की एक सरणी गिरफ्तारी परिभाषित करें:n.

• इनिशियलाइज़ i :=0 के लिए, जब i

  • गिरफ्तारी [i] :=अंक [i] - x

• योग :=0, अंतिम :=0

• इनिशियलाइज़ करने के लिए मैं :=0, जब i

  • योग:=योग + गिरफ्तारी [i]

• यदि योग>=0, तो -

  • सही लौटें

• प्रारंभ करने के लिए i :=0, j :=k, जब j

  • अंतिम:=अंतिम + गिरफ्तारी[i]

  • योग:=योग + गिरफ्तारी [जे]

  • यदि अंतिम <0, तो -

    • योग :=योग - अंतिम

    • अंतिम:=0

  • यदि योग>=0, तो -

    • सही लौटें

• झूठी वापसी

• मुख्य विधि से निम्न कार्य करें -

• रेट :=0, लो :=-इन्फ, हाई :=इंफ

• जबकि उच्च-निम्न> 10^-5, करें

  • मध्य:=निम्न + (उच्च-निम्न)/2

  • यदि ठीक (मध्य, अंक, के) सत्य है, तो -

    • कम :=मध्य

    • रिट :=मध्य

  • अन्यथा

    • उच्च :=मध्य

• वापसी रिट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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;
   }
};
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