সমস্যা বিবরণ
একটি অ্যারে দেওয়া আছে, আমরা সংখ্যাগুলোর সারি A-কে সর্বোচ্চ Kটি আশেপাশের (নন-এম্পটি) গ্রুপে পার্টিশন করব, তারপর স্কোর হল প্রতিটি গ্রুপের গড়ের যোগফল। সর্বোচ্চ স্কোর কত হতে পারে?
উদাহরণ
যদি ইনপুট অ্যারে হয় {9, 2, 5, 3, 10} তবে আমরা নিচের মতো পার্টিশন করতে পারি:
{9} {2, 5, 3} এবং {10} তাহলে এই পার্টিশনের গড় যোগফল হবে:
9 + (2 + 5 + 3) / 3 + 10 = 22.33
অ্যালগরিদম
এই সমস্যা সমাধানের জন্য আমরা মেমোরাইজেশন টেকনিক ব্যবহার করতে পারি:
- memo[i][k] হল A[i থেকে n-1]-কে সর্বোচ্চ K পার্টে পার্টিশন করার সেরা স্কোর।
- প্রথম গ্রুপে, আমরা A[i থেকে n-1]-কে A[i থেকে j-1] এবং A[j থেকে n-1]-এ পার্টিশন করি, তাহলে আমাদের ক্যান্ডিডেট পার্টিশনের স্কোর হবে average(i, j) + score(j, k-1)), যেখানে average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i)। আমরা এগুলোর মধ্যে সর্বোচ্চ স্কোর নিব।
- মোটামুটি, আমাদের রিকার্সন হল: memo[n][k] = max(memo[n][k], score(memo, i, A, k-1) + average(i, j))।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
double memo[MAX][MAX];
double score(int n, vector<int>& arr, int k) {
if (memo[n][k] > 0) {
return memo[n][k];
}
double sum = 0;
for (int i = n - 1; i > 0; i--) {
sum += arr[i];
memo[n][k] = max(memo[n][k], score(i, arr, k - 1) + sum / (n - i));
}
return memo[n][k];
}
double getLargestSum(vector<int>& arr, int K) {
int n = arr.size();
double sum = 0;
memset(memo, 0.0, sizeof(memo));
for (int i = 0; i < n; i++) {
sum += arr[i];
memo[i + 1][1] = sum / (i + 1);
}
return score(n, arr, K);
}
int main() {
vector<int> arr = {9, 2, 5, 3, 10};
int K = 3;
cout << "Largest sum = " << getLargestSum(arr, K) << endl;
return 0;
}
আউটপুট
Largest sum = 22.3333
