C++ में अधिकतम सबअरे आकार जैसे कि उस आकार के सभी सबअरे का योग k से कम हो

इस ट्यूटोरियल में, हम अधिकतम सबअरे आकार खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे जैसे कि उस आकार के सभी सबअरे का योग k से कम हो।

इसके लिए हमें आकार N की एक सरणी और एक पूर्णांक k प्रदान किया जाएगा। हमारा कार्य सबअरे की लंबाई ढूंढना है जैसे कि दी गई सरणी में उस लंबाई के सभी सब-अरे का योग k से कम या बराबर हो।

उदाहरण

#include<bits/stdc++.h> 
using namespace std; 
// अधिकतम लंबाई सबअरे ढूंढना 
int bsearch(int prefixsum[], int n, int k) { 
    int ans = -1; 
    // बाइनरी सर्च करना 
    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; 
} 
// अधिकतम सबअरे आकार वापस करना 
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