সর্বোচ্চ সাবঅ্যারে আকার যাতে সকল সাবঅ্যারের যোগফল k-এর চেয়ে কম (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n সংখ্যক ধনাত্মক পূর্ণসংখ্যা সমন্বিত একটি অ্যারে arr[] এবং একটি পূর্ণসংখ্যা k দেওয়া আছে। আমাদের কাজ হল সর্বোচ্চ সাবঅ্যারে আকার খুঁজে বের করার প্রোগ্রাম তৈরি করা যাতে ওই আকারের সকল সাবঅ্যারের যোগফল k-এর চেয়ে কম বা সমান হয়।

আমাদের সাবঅ্যারের সর্বোচ্চ আকার বের করতে হবে, যেন অ্যারেতে উপাদান থেকে ওই আকারের সকল সাবঅ্যারে তৈরি করলে তাদের উপাদানগুলোর যোগফল k-এর চেয়ে কম বা সমান হয়।

arr[n] = {4, 1, 3, 2}, k = 9

3

আকার ৩-এর সকল সাবঅ্যারে এবং তাদের যোগফল:

{4, 1, 3} = 8
{1, 3, 2} = 6
আকার ৩-এর সকল সাবঅ্যারের যোগফল k-এর চেয়ে কম বা সমান।

একটি সহজ সমাধান হল সাবঅ্যারে খুঁজে বের করা যেটির আকার k-এর চেয়ে বড় হতে পারে। এর জন্য, আমরা একটি প্রিফিক্স সাম (prefix sum) তৈরি করব যা দেওয়া ইনডেক্স পর্যন্ত উপাদানগুলোর যোগফল নির্দেশ করবে। এই প্রিফিক্স সামের জন্য, আমরা সর্বোচ্চ ফলাফল খুঁজে বের করব যা k-এর চেয়ে কম এবং এর ইনডেক্স আমাদের ফলাফল হবে। এখানে, আমরা এই факт ব্যবহার করেছি যে যদি কোনো আকারের জন্য প্রিফিক্স সাম k-এর চেয়ে বড় হয়, এবং বাকিগুলো কম হয়, তবে আকার -১ দৈর্ঘ্যের সকল সাবঅ্যারের যোগফল k-এর চেয়ে কম হবে।

#include 
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];
    
    // আকার সার্চ করা
    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;
}

This method is efficient but a better approach can be made to solve the problem,

এই পদ্ধতিতে, আমরা স্লাইডিং উইন্ডো (sliding window) পদ্ধতি ব্যবহার করব সাবঅ্যারের যোগফল বের করার জন্য। সব উপাদান নিয়ে শুরু করে আমরা আকার বের করব যতক্ষণ না যোগফল k-এর উপরে যায়। এবং তারপর আকার - ১ ফেরত দিব যা সকল সাবঅ্যারের যোগফল k-এর চেয়ে কম বা সমান হওয়ার সর্বোচ্চ আকার।

#include 
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