C++-এ সর্বোচ্চ সাবঅ্যারে আকার যাতে সাবঅ্যারে যোগফল k-র চেয়ে কম (Maximum subarray size, such that all subarrays of that size have sum less than k)

এই টিউটোরিয়ালে আমরা সর্বোচ্চ সাবঅ্যারে আকার বের করব যাতে সেই আকারের সব সাবঅ্যারের যোগফল k-র চেয়ে কম বা সমান হয়।

একটি অ্যারে (আকার N) এবং পূর্ণসংখ্যা k দেওয়া থাকবে। সেই আকারের সাবঅ্যারে খুঁজে বের করতে হবে যাতে প্রদত্ত অ্যারেতে সেই দৈর্ঘ্যের সব সাব-অ্যারের যোগফল k-র চেয়ে কম বা সমান হয়।

উদাহরণ

#include<bits/stdc++.h>
using namespace std;
//finding maximum length subarray
int bsearch(int prefixsum[], int n, int k) {
    int ans = -1;
    //performing binary search
    int left = 1, right = n;
    while (left <= right) {
        int mid = (left + right) / 2;
        int i;
        for (i = mid; i <= n; i++) {
            if (prefixsum[i] - prefixsum[i - mid] > k)
                break;
        }
        if (i == n + 1) {
            left = mid + 1;
            ans = mid;
        }
        else right = mid - 1;
    }
    return ans;
}
//returning maximum subarray size
int maxSize(int arr[], int n, int k) {
    int prefixsum[n + 1];
    memset(prefixsum, 0, sizeof(prefixsum));
    for (int i = 0; i < n; i++)
        prefixsum[i + 1] = prefixsum[i] + arr[i];
    return bsearch(prefixsum, n, k);
}
int main() {
    int arr[] = {1, 2, 10, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 14;
    cout << maxSize(arr, n, k) << endl;
    return 0;
}

আউটপুট

2