একটি অ্যারে এবং একটি সাম দেওয়া আছে। সাবঅ্যারে যেন দিয়ে गये সামের চেয়ে ছোট বা সমান হয়, এমন সবচেয়ে বড় সাবঅ্যারে সাম বের করতে হবে।
উদাহরণ: array = {3, 5, 1, 8, 2, 9}, sum = 25 -> আউটপুট: 25 (সাবঅ্যারে {5,1,8,2,9})।
সহজ পদ্ধতিতে O(n²) টাইম লাগে। দক্ষ পদ্ধতি: স্লাইডিং উইন্ডো (sliding window)। কারেন্ট সাম ম্যাক্স সামের সাথে তুলনা করে উইন্ডো বাড়িয়ে বা ছোট করে সমাধান করব।
উদাহরণ
#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
