C++-এ সর্বোচ্চ গড়ের যোগফল সমস্যা সমাধান

মান করুন আমরা সংখ্যाओं的一行 A-কে সর্বোচ্চ Kটি আডজেসেন্ট গ্রুপে পার্টিশন করি, তারপর স্কোর হিসেবে প্রতিটি গ্রুপের গড়ের যোগফল ধরি। আমাদের বের করতে হবে আমরা সর্বোচ্চ কত স্কোর অর্জন করতে পারি।

যদি A = [9,1,2,3,9] এবং K = 3 হয়, তবে ফলাফল হবে ২০, কারণ সেরা পার্টিশন হল [9], [1, 2, 3], [9]। তাই উত্তর 9 + (1 + 2 + 3) / 3 + 9 = ২০। আমরা [9, 1], [2], [3, 9] হিসেবেও পার্টিশন করতে পারতাম।

এটি সমাধান করার জন্য নিচের ধাপগুলি অনুসরণ করুন −

• একটি ম্যাট্রিক্স dp সংজ্ঞায়িত করুন
• একটি রিকারসিভ মেথড solve() সংজ্ঞায়িত করুন, এটি অ্যারে A, ইনডেক্স এবং k নেবে
• যদি index >= A.size() হয়, তবে 0 ফেরত দিন
• যদি k = 0 হয়, তবে -100000 ফেরত দিন
• যদি dp[index, k] != -1 হয়, তবে dp[index, k] ফেরত দিন
• ret := -inf এবং sum := 0
• i = index থেকে A.size() - 1 পর্যন্ত
  • sum := sum + A[i]
  • ret := max(ret, sum/(i - index + 1) + solve(A, i + 1, k - 1))
• dp[index, 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