এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে যা এন ধনাত্মক পূর্ণসংখ্যা এবং একটি পূর্ণসংখ্যা k নিয়ে গঠিত। আমাদের কাজ হল ম্যাক্সিমামসুবারের আকার খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা, যাতে সেই আকারের সমস্ত সাবয়ারের যোগফল k থেকে কম থাকে৷
সমস্যা বর্ণনা − আমাদের একটি সাবয়ারের সবচেয়ে বড় আকার খুঁজে বের করতে হবে, যেমন অ্যারের উপাদানগুলি থেকে আকারে তৈরি করা সমস্ত সাবয়ারের উপাদানগুলির যোগফল k এর থেকে কম বা সমান হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[n] = {4, 1, 3, 2}, k = 9 আউটপুট
3
ব্যাখ্যা
3 আকারের সমস্ত সাবঅ্যারে এবং তাদের যোগফল −
{4, 1, 3} = 8
{1, 3, 2} = 6
The sum of all subarrays of size 3 is less than or equal to k. সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল সাবারে খুঁজে বের করা যার আকার k এর থেকে বেশি হতে পারে। এর জন্য, আমরা একটি প্রিফিক্স যোগফল তৈরি করব যা প্রদত্ত সূচক পর্যন্ত উপাদানগুলির যোগফলকে নির্দেশ করে। এই উপসর্গ যোগফলের জন্য, আমরা সর্বাধিক ফলাফল পাব যা k এর থেকে কম এবং এর সূচকটি হবে আমাদের ফলাফল। এখানে, আমরা এই সত্যটি ব্যবহার করেছি যে উপসর্গের যোগফল যদি কোন আকারের জন্য k এর থেকে বড় হয়, এবং বাকি সকলের যোগফল থাকে। কম, তাহলে −1 দৈর্ঘ্যের সমস্ত সাবয়ারের যোগফল k-এর থেকে কম হবে।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include<iostream>
using namespace std;
int calcSubArraySize(int arr[], int n, int k){
int prefixSum[n + 1];
prefixSum[0] = 0;
for (int i = 0; i < n; i++)
prefixSum[i + 1] = prefixSum[i] + arr[i];
// Searching size
int maxLen = −1;
int start = 1, end = n;
int mid, i;
while (start <= end){
int mid = (start + end) / 2;
for (i = mid; i <= n; i++){
if (prefixSum[i] − prefixSum[i − mid] > k)
break;
}
if (i == n + 1){
start = mid + 1;
maxLen = mid;
}
else
end = mid − 1;
}
return maxLen;
}
int main(){
int arr[] = {4, 1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 9;
cout<<"The maximum subarray size, such that all subarrays of that
size have sum less than k is "<<calcSubArraySize(arr, n, k);
return 0;
} আউটপুট
এই পদ্ধতিটি কার্যকর কিন্তু সমস্যা সমাধানের জন্য আরও ভালো পদ্ধতি তৈরি করা যেতে পারে,
এই পদ্ধতিতে, আমরা subarray এর যোগফল খুঁজে বের করার জন্য স্লাইডিং উইন্ডো পদ্ধতি ব্যবহার করব। সমস্ত উপাদান গ্রহণ করে শুরু করে আমরা দৈর্ঘ্য খুঁজে পাব যতক্ষণ না যোগফল k এর উপরে থাকে। এবং তারপর দৈর্ঘ্য − 1 ফেরত দিন যা সাবয়ারের সর্বাধিক আকার যার জন্য সমস্ত সাবয়ারের যোগফল 0 এর থেকে কম বা সমান।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int calcSubArraySizeSW(int arr[], int n, int k){
int maxLen = n;
int subArraySum = 0;
int start = 0;
for (int end = 0; end < n; end++){
subArraySum += arr[end];
while (subArraySum > k) {
subArraySum −= arr[start];
start++;
maxLen = min(maxLen, end − start + 1);
if (subArraySum == 0)
break;
}
if (subArraySum == 0) {
maxLen = −1;
break;
}
}
return maxLen;
}
int main(){
int arr[] = { 4, 1, 3, 2, 6 };
int k = 12;
int n = sizeof(arr)/ sizeof(arr[0]);
cout<<"The maximum subarray size, such that all subarrays of that
size have sum less than k is "<<calcSubArraySizeSW(arr, n, k);
return 0;
} আউটপুট
The maximum subarray size, such that all subarrays of that size have sum less than k is 4
