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

इस समस्या में, हमें n धनात्मक पूर्णांकों से युक्त एक सरणी arr[] और एक पूर्णांक k दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो अधिकतम उपसरणी आकार ढूंढे जैसे कि उस आकार की सभी उपसरणियों का योग k से कम हो।

समस्या विवरण

हमें उपसरणी का सबसे बड़ा आकार ढूंढना है, जैसे कि सरणी के तत्वों से बनी उस आकार की सभी उपसरणियों का तत्वों का योग k से कम या बराबर हो।

उदाहरण

इनपुट

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

आउटपुट

3

व्याख्या

आकार 3 की सभी उपसरणियाँ और उनका योग -

{4, 1, 3} = 8 
{1, 3, 2} = 6 
आकार 3 की सभी उपसरणियों का योग k से कम या बराबर है।

समाधान दृष्टिकोण

समस्या का एक सरल समाधान उस उपसरणी को ढूंढना है जिसका आकार k से अधिक योग हो सकता है। इसके लिए, हम एक उपसर्ग योग (prefix sum) बनाएंगे जो दिए गए सूचकांक तक के तत्वों के योग को दर्शाता है। इस उपसर्ग योग के लिए, हम अधिकतम परिणाम ढूंढेंगे जो k से कम हो और इसका सूचकांक हमारा परिणाम होगा। यहां, हमने इस तथ्य का उपयोग किया है कि यदि किसी आकार के लिए उपसर्ग योग k से अधिक है, और बाकी सभी का योग कम है, तो आकार -1 लंबाई की सभी उपसरणियों का योग k से कम होगा।

उदाहरण

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

#include<iostream> 
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; 
}

आउटपुट

यह विधि कुशल है लेकिन समस्या को हल करने के लिए एक बेहतर दृष्टिकोण बनाया जा सकता है,

इस दृष्टिकोण में, हम उपसरणी के योग को ढूंढने के लिए स्लाइडिंग विंडो विधि का उपयोग करेंगे। सभी तत्वों को लेकर शुरू करके हम उस लंबाई को ढूंढेंगे जहां तक योग k से ऊपर रहता है। और फिर लंबाई - 1 वापस करेंगे जो उस उपसरणी का अधिकतम आकार है जिसके लिए सभी उपसरणियों का योग k से कम या बराबर है।

उदाहरण

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

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