इस समस्या में, हमें एक सरणी गिरफ्तारी [] और एक संख्या k दी जाती है। हमारा कार्य है k आकार के एक उप-सरणी का अधिकतम (या न्यूनतम) योग ज्ञात करना।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: गिरफ्तारी [] ={55, 43, 12, 76, 89, 25, 99} , के =2
आउटपुट: 165
स्पष्टीकरण:
आकार 2 के उप-सरणी का योग =76 + 89 =165
. हैसमाधान दृष्टिकोण
समस्या को हल करने का एक आसान तरीका सभी k आकार के सबअरे ढूंढकर और फिर योग को अधिकतम मान के साथ वापस करना है।
एक और तरीका स्लाइडिंग विंडो का उपयोग कर रहा है, हम k आकार की उप-सरणी का योग ज्ञात करेंगे। इसके लिए, अगला k आकार का उप-सरणी, हम अंतिम अनुक्रमणिका तत्व घटाएंगे और अगला अनुक्रमणिका तत्व जोड़ेंगे।
और फिर सबरेरे योग को अधिकतम मूल्य के साथ वापस कर दें।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <iostream>
using namespace std;
int findMaxSumSubarray(int arr[], int n, int k) {
if (n < k) {
cout << "Invalid";
return -1;
}
int maxSum = 0;
for (int i=0; i<k; i++)
maxSum += arr[i];
int curr_sum = maxSum;
for (int i=k; i<n; i++) {
curr_sum += arr[i] - arr[i-k];
maxSum = max(maxSum, curr_sum);
}
return maxSum;
}
int main() {
int arr[] = {55, 43, 12, 76, 89, 25, 99};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout<<"The sum of subarray with max sum of size "<<k<<" is "<<findMaxSumSubarray(arr, n, k);
return 0;
} आउटपुट
The sum of subarray with max sum of size 2 is 165