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

C++ में औसत का सबसे बड़ा योग


मान लीजिए हम संख्याओं की एक पंक्ति A को अधिकतम K आसन्न समूहों में विभाजित करते हैं, फिर हम स्कोर को प्रत्येक समूह के औसत के योग के रूप में सेट करेंगे। हमें यह पता लगाना है कि हम सबसे बड़ा स्कोर क्या प्राप्त कर सकते हैं। मान लीजिए A = [9,1,2,3,9] और K 3 है, तो परिणाम 20 होगा, ऐसा इसलिए है क्योंकि, सबसे अच्छा विकल्प A को [9], [1, 2, 3], [9] में विभाजित करना है। तो उत्तर 9 + (1 + 2 + 3) / 3 + 9 = 20 है। हम A को [9, 1], [2], [3, 9] में भी विभाजित कर सकते थे,

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

  • एक मैट्रिक्स dp परिभाषित करें
  • एक रिकर्सिव मेथड solve() परिभाषित करें, यह सरणी A, इंडेक्स और k लेगा
  • यदि इंडेक्स >= A का आकार, तो 0 लौटाएं
  • यदि k 0 है, तो -100000 लौटाएं
  • यदि dp[इंडेक्स, k] -1 नहीं है, तो dp[इंडेक्स, k] लौटाएं
  • ret := -inf और sum := 0
  • i को इंडेक्स से A के आकार - 1 की रेंज में
    • sum := sum + A[i]
    • ret := ret का अधिकतम और sum/(i - इंडेक्स + 1) + solve(A, i + 1, k - 1)
  • dp[इंडेक्स, k] := ret सेट करें और लौटाएं।
  • मुख्य मेथड से, निम्नलिखित करें -
  • n := A का आकार
  • dp := एक मैट्रिक्स n x (K + 1), इसे -1 से भरें
  • solve(A, 0, K) लौटाएं

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

उदाहरण

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

class Solution {
public:
    vector < vector <double> > dp;
    double solve(vector <int>& A, int idx, int k){
        if(idx >= A.size()) return 0;
        if(!k) return -100000;
        if(dp[idx][k] != -1) return dp[idx][k];
        double ret = INT_MIN;
        double sum = 0;
        for(int i = idx; i < A.size(); i++){
            sum += A[i];
            ret = max(sum / (i - idx + 1) + solve(A, i + 1, k - 1), ret);
        }
        return dp[idx][k] = ret;
    }
    double largestSumOfAverages(vector<int>& A, int K) {
        int n = A.size();
        dp = vector < vector <double> > (n, vector <double>(K + 1, -1));
        return solve(A, 0, K);
    }
};

main(){
    vector<int> v = {9,1,2,3,9};
    Solution ob;
    cout << (ob.largestSumOfAverages(v, 3));
}

इनपुट

[9,1,2,3,9] 3

आउटपुट

20

  1. - C++ में योग k से बड़ा वाला सबसे बड़ा सबअरे

    इस ट्यूटोरियल में, हम एक प्रोग्राम लिखने जा रहे हैं जो योग k से बड़ा वाला सबसे बड़ा सबअरे ढूंढता है। आइए समस्या को हल करने के चरण देखते हैं। सरणी आरंभ करें। सरणी पर पुनरावृति करें और प्रत्येक इंडेक्स पर योग को इंडेक्स के साथ एक वेक्टर में स्टोर करें। उपरोक्त योगों को योग और इंडेक्स के आधार पर क्रम

  1. - C++ में n के सभी भाजकों में अंकों का सबसे बड़ा योग ढूंढें

    इस समस्या में, हमें एक पूर्णांक n दिया गया है। हमारा कार्य n के सभी भाजकों में अंकों का सबसे बड़ा योग ढूंढना है। समस्या विवरण: यहां, हम संख्या n के उस भाजक को ढूंढेंगे जिसके अंकों का योग सबसे बड़ा है। समस्या को समझने के लिए एक उदाहरण लेते हैं, इनपुट: 18 आउटपुट: 9 व्याख्या: 18 के सभी भाजक हैं 1, 2,

  1. C++ में ट्री में सबसे बड़ा उपट्री योग ढूंढें C++ में ट्री में सबसे बड़ा उपट्री योग ढूंढें

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य ट्री में सबसे बड़ा उपट्री योग ढूंढना है। समस्या विवरण: बाइनरी ट्री में धनात्मक और ऋणात्मक दोनों मान होते हैं। और हमें वह उपट्री ढूंढनी है जिसमें नोड्स का अधिकतम योग हो। समस्या को समझने के लिए एक उदाहरण लेते हैं, आउटपुट: 13 व्याख्या: बाएं