ধরুন আমরা সংখ্যার একটি সারি 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],
তেও ভাগ করতে পারতাম।এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ম্যাট্রিক্স ডিপি সংজ্ঞায়িত করুন
- একটি পুনরাবৃত্ত পদ্ধতি সংজ্ঞায়িত করুন সমাধান(), এটি অ্যারে, সূচক এবং k নেবে
- যদি সূচী>=A এর আকার, তাহলে 0 ফেরত দিন
- যদি k 0 হয়, তাহলে -100000 ফেরত দিন
- যদি dp[index, k] না হয় – 1, তাহলে dp[index, k] ফেরত দিন
- ret :=-inf এবং যোগফল :=0
- আমি রেঞ্জ ইনডেক্স থেকে A – 1 এর আকারের জন্য
- সমষ্টি :=যোগফল + A[i]
- ret :=ret এবং যোগফলের সর্বোচ্চ/(i – সূচক + 1) + সমাধান (A, i + 1, k – 1)
- dp[index, k] সেট করুন :=ret এবং রিটার্ন।
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- n :=A এর আকার
- dp :=একটি ম্যাট্রিক্স n x (K + 1), এটি – 1 দিয়ে পূরণ করুন
- রিটার্ন সলভ (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
