मान लीजिए हम संख्याओं की एक पंक्ति 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