Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


मान लीजिए हमारे पास 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 := 0
  • i := 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 - last
      • last := 0
    • यदि sum >= 0, तो true वापस करें
  • false वापस करें
  • मुख्य विधि से निम्नलिखित करें:
    • ret := 0, low := -inf, high := inf
    • high - low > 10^-5 होने तक लूप चलाएं:
      • mid := low + (high - low) / 2
      • यदि ok(mid, nums, k) सत्य है, तो:
        • low := mid
        • ret := 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
  1. - C++ में ऐरे का अधिकतम औसत योग पार्टीशन

    समस्या कथन एक ऐरे दिया गया है, हम संख्याओं की एक पंक्ति A को अधिकतम K आसन्न (गैर-खाली) समूहों में पार्टीशन करते हैं, फिर स्कोर प्रत्येक समूह के औसत का योग होता है। अधिकतम स्कोर क्या हो सकता है? उदाहरण यदि इनपुट ऐरे है {9, 2, 5, 3, 10} तो हम ऐरे को निम्नानुसार पार्टीशन कर सकते हैं: {9} {2, 5, 3} और

  1. - 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 आकार

  1. - पायथन में अधिकतम उपसरणी

    मान लीजिए हमारे पास एक पूर्णांक सरणी A है। हमें सन्निकट उपसरणी ढूंढनी है जिसकी लंबाई कम से कम एक हो, और जिसका योग सबसे बड़ा हो, और उसका योग भी वापस करना है। यदि सरणी A [-2,1,-3,4,-1,2,1,-5,4] जैसी है, तो योग 6 होगा। और उपसरणी [4, -1, 2, 1] होगी। इसे हल करने के लिए हम डायनामिक प्रोग्रामिंग दृष्टिकोण