এই সমস্যায়, আমাদেরকে ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে এবং একটি সংখ্যা k দেওয়া হয়েছে। আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা প্রদত্ত আকার(k) এর সর্বাধিক দুটি ননওভারল্যাপিং সাবয়ারের সমষ্টি খুঁজে পাবে।
সুতরাং, মূলত আমাদের কাছে দুটি প্রিন্ট দুটি নন-ওভারল্যাপিং (স্বতন্ত্র) সাবয়ারে রয়েছে যার সর্বাধিক যোগফল রয়েছে এবং আকার k।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট −
array = {7, 1, 6, 9, 2} , k = 2 আউটপুট −
{7, 1} , {6, 9} ব্যাখ্যা −
all subarrays of size 2.
{7, 1} : sum = 7+1 = 8
{1, 6} : sum = 1+6 = 7
{6, 9} : sum = 6+9 = 15
{9, 2} : sum = 9+2 = 11
Two non-overlapping subarrays with max sums are {7,1} and {6,9} এই সমস্যাটি সমাধান করার জন্য, একটি সহজ সমাধান হবে সমস্ত সাববারে এবং তাদের যোগফল খুঁজে বের করা এবং তারপরে দুটি সর্বোচ্চ সাব্যারে চেক করুন যা একে অপরকে ওভারল্যাপ করে না।
সমস্যা সমাধানের একটি কার্যকর পদ্ধতি উপসর্গ যোগ অ্যারে ব্যবহার করা হবে যা অ্যারের উপাদান পর্যন্ত সমস্ত উপাদানের যোগফল সংরক্ষণ করে। এবং সর্বাধিক যোগফল সহ সাবয়ারে খুঁজে পেতে k উপাদানগুলির জন্য চেক করুন।
উদাহরণ
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
#include <bits/stdc++.h>
using namespace std;
int findSubArraySum(int sum[], int i, int j){
if (i == 0)
return sum[j];
else
return (sum[j] - sum[i - 1]);
}
void maxSubarray(int arr[],int N, int K){
int prefixsum[N];
prefixsum[0] = arr[0];
for (int i = 1; i < N; i++)
prefixsum[i] = prefixsum[i - 1] + arr[i];
pair<int, int> resIndex = make_pair(N - 2 * K, N - K);
int maxSubarraySum = findSubArraySum(prefixsum, N - 2 * K, N - K - 1) + findSubArraySum(prefixsum, N - K, N - 1);
pair<int, int> secondSubarrayMax = make_pair(N - K, findSubArraySum(prefixsum, N - K, N - 1));
for (int i = N - 2 * K - 1; i >= 0; i--){
int cur = findSubArraySum(prefixsum, i + K, i + 2 * K - 1);
if (cur >= secondSubarrayMax.second)
secondSubarrayMax = make_pair(i + K, cur);
cur = findSubArraySum(prefixsum, i, i + K - 1) + secondSubarrayMax.second;
if (cur >= maxSubarraySum){
maxSubarraySum = cur;
resIndex = make_pair(i, secondSubarrayMax.first);
}
}
cout<<"{ ";
for (int i = resIndex.first; i <resIndex.first + K; i++)
cout<<arr[i]<<" ";
cout<<"}"<<endl<<"{ ";
for (int i = resIndex.second; i < resIndex.second + K; i++)
cout<<arr[i]<<" ";
cout<<"}"<<endl;
}
int main(){
int arr[] = {2, 5, 1, 2, 7, 3, 0};
int N = sizeof(arr) / sizeof(int);
int K = 2;
cout<<"Two non-overlapping subarrays with maximum sum are \n";
maxSubarray(arr, N, K);
return 0;
} আউটপুট
Two non-overlapping subarrays with maximum sum are
{ 2 5 }
{ 7 3 } 