এই সমস্যায়, আমাদের একটি অ্যারে এবং একটি যোগফল দেওয়া হয়েছে। আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা c++ এ প্রদত্ত যোগফলের থেকে কম বা সমান সমষ্টির সর্বাধিক যোগফল সাবয়ারে খুঁজে পাবে।
আমাদেরকে n এর থেকে কম বা সমান যেকোন দৈর্ঘ্যের সাবঅ্যারে খুঁজে বের করতে হবে যার যোগফল প্রদত্ত যোগফলের থেকে কম বা সমান।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট − অ্যারে ={3, 5, 1, 8, 2, 9}, যোগফল =25
আউটপুট − ২৫
ব্যাখ্যা − 25 এর কম বা সমান সমষ্টি সহ সাব্যারেগুলি হল {5, 1, 8, 2, 9}
সর্বাধিক যোগফল সাবঅ্যারে খোঁজার একটি সহজ পদ্ধতি হল অ্যারের উপর পুনরাবৃত্তি করা এবং সমস্ত সাবয়ারের যোগফল খুঁজে বের করা এবং তারপরে নিকটতম বা সমান যোগফল খুঁজে বের করা। কিন্তু এই পদ্ধতিতে O(n*n) এর সময় জটিলতা থাকবে কারণ দুটি লুপ প্রয়োজন।
এই সমস্যাটি সমাধান করার জন্য একটি আরও কার্যকর পদ্ধতি হল স্লাইডিং উইন্ডো ব্যবহার করে পদ্ধতি যেটিতে আমরা সর্বাধিক যোগফলের সাথে বর্তমান যোগফল পরীক্ষা করব এবং তুলনার ভিত্তিতে উইন্ডোতে উপাদান যোগ বা বিয়োগ করব।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int findMax(int a, int b){
if(a>b)
return a;
return b;
}
int maxSumsubarray(int arr[], int n, int maxSum){
int sum = arr[0], overallMax = 0, start = 0;
for (int i = 1; i < n; i++) {
if (sum <= maxSum)
overallMax = findMax(overallMax, sum);
while (sum + arr[i] > maxSum && start < i) {
sum -= arr[start];
start++;
}
sum += arr[i];
}
if (sum <= maxSum)
overallMax = findMax(overallMax, sum);
return overallMax;
}
int main(){
int arr[] = {3, 1, 4, 7, 2, 9, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 20;
cout<<"The maximum sum of subarray with sum less than or equal to "<<sum<<" is "<<maxSumsubarray(arr, n, sum);
return 0;
} আউটপুট
The maximum sum of subarray with sum less than or equal to 20 is 18
