এই সমস্যায়, আমাদেরকে একটি অ্যারে arr[] এবং একটি সংখ্যা k দেওয়া হয়েছে। আমাদের কাজ হল k আকারের একটি সাবয়ারের সর্বাধিক (বা সর্বনিম্ন) যোগফল খুঁজে বের করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: arr[] ={55, 43, 12, 76, 89, 25, 99} , k =2
আউটপুট: 165
ব্যাখ্যা:
সাইজ 2 এর সাবয়ারের যোগফল =76 + 89 =165
সমাধান পদ্ধতি
সমস্যা সমাধানের একটি সহজ পদ্ধতি হল সমস্ত k আকারের সাবয়ারে খুঁজে বের করা এবং তারপর সর্বাধিক মান সহ যোগফল ফেরত দেওয়া৷
আরেকটি পদ্ধতি স্লাইডিং উইন্ডো ব্যবহার করছে আমরা k আকারের সাবয়ারের সমষ্টি খুঁজে পাব। এর জন্য, পরবর্তী k আকারের সাবয়ারে, আমরা শেষ সূচক উপাদানটি বিয়োগ করব এবং পরবর্তী সূচক উপাদান যোগ করব।
এবং তারপর সর্বোচ্চ মান সহ সাব্যারে যোগফল ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
int findMaxSumSubarray(int arr[], int n, int k) {
if (n < k) {
cout << "Invalid";
return -1;
}
int maxSum = 0;
for (int i=0; i<k; i++)
maxSum += arr[i];
int curr_sum = maxSum;
for (int i=k; i<n; i++) {
curr_sum += arr[i] - arr[i-k];
maxSum = max(maxSum, curr_sum);
}
return maxSum;
}
int main() {
int arr[] = {55, 43, 12, 76, 89, 25, 99};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout<<"The sum of subarray with max sum of size "<<k<<" is "<<findMaxSumSubarray(arr, n, k);
return 0;
} আউটপুট
The sum of subarray with max sum of size 2 is 165
