এই সমস্যায়, আমাদের n আকারের একটি অ্যারে অ্যারে [] এবং একটি পূর্ণসংখ্যা k দেওয়া হয়েছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যাতে একটি অ্যারেতে সর্বাধিক সাবয়ারের যোগফল বারবার সংযুক্ত করার পরে তৈরি করা হয়৷
সমস্যা বর্ণনা − আমরা দেখতে পাব যে অ্যারে থেকে সাবয়ারের সর্বোচ্চ যোগফল নেওয়া হয়েছে যা arr, k বার পুনরাবৃত্তি করার পরে তৈরি হয়৷
উদাহরণ
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক৷৷
ইনপুট
arr[] = {−9, −5, 14, 6} k = 2 আউটপুট
26
ব্যাখ্যা
New array after repeating : {−9, −5, 14, 6, −9, −5, 14, 6}
Subarray with maximum sum = {14, 6, −9, −5, 14, 6}
Sum = 26 সমাধান পদ্ধতি
একটি সহজ সমাধান হল একটি নতুন অ্যারে তৈরি করা যা arr[], k টাইমকে একত্রিত করার পরে গঠিত হবে এবং তারপর সর্বাধিক যোগফল সহ সাবয়ারে খুঁজে বের করা। এর জন্য, সর্বোত্তম পদ্ধতিটি হবে কাদানের অ্যালগরিদম ব্যবহার করা।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
int newArr[2*n];
for(int i = 0; i < k*n; i++)
newArr[i] = arr[i%n];
int maxSum = −1000, sum = 0;
for (int i = 0; i < k*n; i++) {
sum = sum + newArr[i];
if (maxSum < sum)
maxSum = sum;
if (sum < 0)
sum = 0;
}
return maxSum;
}
int main(){
int arr[] = { −9, −5, 14, 6 };
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum subarray sum in an array created after repeated concatenation is "<<calcMaxSubArraySum(arr, n, k);
return 0;
} আউটপুট
The maximum subarray sum in an array created after repeated concatenation is 26
এই পদ্ধতিটি ভাল তবে মডুলার গাণিতিক ব্যবহার করে সমস্যা সমাধানের জন্য আরও কার্যকর পদ্ধতি।
মডুলার পাটিগণিত যখন আমরা সমীকরণের অবশিষ্টাংশ পেতে মডুলো অপারেটর ব্যবহার করি।
সমস্যা সমাধানের জন্য, আমরা বারবার সংযোজন করে থিয়ারে তৈরি করার পরিবর্তে মডুলার গাণিতিক ব্যবহার করব। বাকি সমাধান একই থাকে।
উদাহরণ
আমাদের সমাধানের কাজটি চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
int maxSum = −1000, sum = 0;
for (int i = 0; i < k*n; i++) {
sum = sum + arr[i%n];
if (maxSum < sum)
maxSum = sum;
if (sum < 0)
sum = 0;
}
return maxSum;
}
int main(){
int arr[] = { −9, −5, 14, 6 };
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum subarray sum in an array created after
repeated concatenation is "<<calcMaxSubArraySum(arr, n, k);
return 0;
} আউটপুট
The maximum subarray sum in an array created after repeated concatenation is 26
