इस समस्या में, हमें n धनात्मक पूर्णांकों और पूर्णांक k से मिलकर बना एक सरणी arr[] दिया गया है। हमारा काम मैक्सिममसुबरे आकार को खोजने के लिए एक प्रोग्राम बनाना है, जैसे कि उस आकार के सभी उप-सरणी का योग k से कम हो।
समस्या का विवरण - हमें एक सबअरे का सबसे बड़ा आकार खोजने की जरूरत है, जैसे कि एरे के तत्वों से आकार से बने सभी सबअरे में के से कम या उसके बराबर तत्वों का योग होगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[n] = {4, 1, 3, 2}, k = 9 आउटपुट
3
स्पष्टीकरण
आकार 3 के सभी उप-सरणी और उनका योग −
{4, 1, 3} = 8
{1, 3, 2} = 6
The sum of all subarrays of size 3 is less than or equal to k. समाधान दृष्टिकोण
समस्या का एक सरल समाधान उप-सरणी का पता लगाना है जिसका आकार k से बड़ा हो सकता है। इसके लिए, हम एक उपसर्ग योग बनाएंगे जो दिए गए सूचकांक तक तत्वों के योग को दर्शाता है। इस उपसर्ग योग के लिए, हम अधिकतम परिणाम पाएंगे जो 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];
// Searching size
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 लौटाएं, जो कि उप-सरणी का अधिकतम आकार है जिसके लिए सभी उप-सरणी का योग 0 से कम या उसके बराबर है।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#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है