সমস্যা বিবৃতি
একটি অ্যারে এবং দুটি সংখ্যা M এবং K দেওয়া হয়েছে। আমাদের অ্যারেতে K (নন-ওভারল্যাপিং) আকারের সর্বাধিক M সাবয়ারের যোগফল খুঁজে বের করতে হবে। (অ্যারের ক্রম অপরিবর্তিত থাকে)। K হল সাববারের আকার এবং M হল সাববারের গণনা। এটা অনুমান করা যেতে পারে যে অ্যারের আকার m*k এর চেয়ে বেশি। যদি মোট অ্যারের আকার k এর একাধিক না হয়, তাহলে আমরা আংশিক শেষ অ্যারে নিতে পারি।
উদাহরণ
যদি দেওয়া অ্যারে হয় ={2, 10, 7, 18, 5, 33, 0}। N =7, M =3 এবং K =1 তাহলে আউটপুট হবে 61 যেহেতু উপসেট হল −
{33, 18, 10} অ্যালগরিদম
- আমরা একটি প্রিসাম অ্যারে তৈরি করি, যেটিতে প্রদত্ত অ্যারেতে ‘সূচী’ থেকে ‘ইনডেক্স + কে’ পর্যন্ত সমস্ত উপাদানের সমষ্টি রয়েছে। এবং সমষ্টি অ্যারের আকার হবে n+1-k
- এখন যদি আমরা k আকারের সাবয়ারে অন্তর্ভুক্ত করি, তাহলে আমরা সেই সাবয়েরের কোনো উপাদানকে আবার অন্য কোনো সাবরেতে অন্তর্ভুক্ত করতে পারি না কারণ এটি ওভারল্যাপিং সাবয়ারে তৈরি করবে। তাই আমরা অন্তর্ভুক্ত সাব্যারেগুলির k উপাদানগুলিকে বাদ দিয়ে রিকার্সিভ কল করি
- যদি আমরা একটি সাবঅ্যারে বাদ দেই তাহলে আমরা সেই সাবয়ারের পরবর্তী k-1 উপাদানগুলিকে অন্যান্য সাবঅ্যারেতে ব্যবহার করতে পারি তাই আমরা সেই subarray-এর প্রথম উপাদানটি বাদ দিয়ে রিকার্সিভ কল করব।
- শেষে সর্বোচ্চ (অধিভুক্ত সমষ্টি, বাদ যোগফল) ফেরত দিন
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void calculatePresumArray(int presum[], int arr[], int n, int k) {
for (int i = 0; i < k; i++) {
presum[0] += arr[i];
}
for (int i = 1; i <= n - k; i++) {
presum[i] += presum[i-1] + arr[i+k-1] - arr[i- 1];
}
}
int maxSumMnonOverlappingSubarray(int presum[], int m, int size, int k, int start) {
if (m == 0)
return 0;
if (start > size - 1)
return 0;
int mx = 0;
int includeMax = presum[start] + maxSumMnonOverlappingSubarray(presum, m - 1, size, k, start + k);
int excludeMax = maxSumMnonOverlappingSubarray(presum, m, size, k, start + 1);
return max(includeMax, excludeMax);
}
int main() {
int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
int n = sizeof(arr)/sizeof(arr[0]);
int m = 3, k = 1;
int presum[n + 1 - k] = { 0 };
calculatePresumArray(presum, arr, n, k);
cout << "Maximum sum = " << maxSumMnonOverlappingSubarray(presum, m, n + 1 - k, k, 0) << endl;
return 0;
} যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেআউটপুট
Maximum sum = 61
