मान लीजिए कि हम संख्या A की एक पंक्ति को अधिक से अधिक K आसन्न समूहों में विभाजित करते हैं, तो हम स्कोर को प्रत्येक समूह के औसत के योग के रूप में सेट करेंगे। हमें यह पता लगाना होगा कि हम सबसे बड़ा स्कोर क्या हासिल कर सकते हैं। मान लीजिए ए =[9,1,2,3,9] और के 3 है, तो परिणाम 20 होगा, ऐसा इसलिए है, क्योंकि ए को [9], [1, 2, 3] में विभाजित करना सबसे अच्छा विकल्प है। [9]। तो उत्तर 9 + (1 + 2 + 3) / 3 + 9 =20 है। हम A को [9, 1], [2], [3, 9],
में भी विभाजित कर सकते थे।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- मैट्रिक्स डीपी परिभाषित करें
- एक पुनरावर्ती विधि को परिभाषित करें हल (), यह सरणी A, अनुक्रमणिका और k लेगा
- यदि अनुक्रमणिका>=A का आकार है, तो 0 लौटाएं
- अगर k 0 है, तो -100000 वापस करें
- अगर dp[index, k] -1 नहीं है, तो dp[index, k] लौटाएं
- रिट:=-इन्फ और योग:=0
- आई के लिए रेंज इंडेक्स में ए - 1 के आकार के लिए
- योग :=योग + ए[i]
- ret :=अधिकतम रिट और योग/(i - अनुक्रमणिका + 1) + हल करें (A, i + 1, k – 1)
- dp[index, k] :=ret और return सेट करें।
- मुख्य विधि से, निम्न कार्य करें -
- n :=A का आकार
- dp:=एक मैट्रिक्स n x (K + 1), इसे - 1 से भरें
- रिटर्न सॉल्व (ए, 0, के)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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