समस्या कथन
एक सरणी और दो संख्या M और K को देखते हुए। हमें सरणी में K (गैर-अतिव्यापी) आकार के अधिकतम M उप-सरणी का योग खोजने की आवश्यकता है। (सरणी का क्रम अपरिवर्तित रहता है)। K सबअरे का आकार है और M सबअरे की गिनती है। यह माना जा सकता है कि सरणी का आकार m*k से अधिक है। यदि कुल सरणी आकार k का गुणज नहीं है, तो हम आंशिक अंतिम सरणी ले सकते हैं।
उदाहरण
यदि दिया गया सरणी ={2, 10, 7, 18, 5, 33, 0} है। एन =7, एम =3 और के =1 तो आउटपुट 61 होगा क्योंकि सबसेट है -
{33, 18, 10} एल्गोरिदम
- हम एक अनुमान सरणी बनाते हैं, जिसमें दिए गए सरणी में 'इंडेक्स' से 'इंडेक्स + के' तक सभी तत्वों के प्रत्येक इंडेक्स योग में शामिल होता है। और योग सरणी का आकार होगा n+1-k
- अब अगर हम आकार k के सबअरे को शामिल करते हैं, तो हम उस सबएरे के किसी भी तत्व को फिर से किसी अन्य सबएरे में शामिल नहीं कर सकते क्योंकि यह ओवरलैपिंग सबएरे बनाएगा। इसलिए हम शामिल किए गए सबअरे के k तत्वों को छोड़कर रिकर्सिव कॉल करते हैं
- अगर हम एक सबअरे को बाहर करते हैं तो हम उस सबएरे के अगले k-1 एलिमेंट को अन्य सबएरे में इस्तेमाल कर सकते हैं, इसलिए हम उस सबएरे के पहले एलिमेंट को छोड़कर रिकर्सिव कॉल करेंगे।
- आखिरी बार अधिकतम (शामिल राशि, बहिष्कृत राशि) लौटाएं
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void calculatePresumArray(int presum[], int arr[], int n, int k) {
for (int i = 0; i < k; i++) {
presum[0] += arr[i];
}
for (int i = 1; i <= n - k; i++) {
presum[i] += presum[i-1] + arr[i+k-1] - arr[i- 1];
}
}
int maxSumMnonOverlappingSubarray(int presum[], int m, int size, int k, int start) {
if (m == 0)
return 0;
if (start > size - 1)
return 0;
int mx = 0;
int includeMax = presum[start] + maxSumMnonOverlappingSubarray(presum, m - 1, size, k, start + k);
int excludeMax = maxSumMnonOverlappingSubarray(presum, m, size, k, start + 1);
return max(includeMax, excludeMax);
}
int main() {
int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
int n = sizeof(arr)/sizeof(arr[0]);
int m = 3, k = 1;
int presum[n + 1 - k] = { 0 };
calculatePresumArray(presum, arr, n, k);
cout << "Maximum sum = " << maxSumMnonOverlappingSubarray(presum, m, n + 1 - k, k, 0) << endl;
return 0;
} जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
आउटपुट
Maximum sum = 61