C++ में आकार K के M नॉन-ओवरलैपिंग सबएरे का अधिकतम योग

समस्या कथन

एक ऐरे और दो संख्याएं M और K दी गई हैं। हमें ऐरे में आकार K के अधिकतम M सबएरे का योग ढूंढना है (नॉन-ओवरलैपिंग)। (ऐरे का क्रम अपरिवर्तित रहता है)। K सबएरे का आकार है और M सबएरे की संख्या है। यह माना जा सकता है कि ऐरे का आकार m*k से अधिक है। यदि कुल ऐरे का आकार k का गुणक नहीं है, तो हम आंशिक अंतिम ऐरे ले सकते हैं।

उदाहरण

यदि दिया गया ऐरे है = {2, 10, 7, 18, 5, 33, 0}. N = 7, M = 3 और K = 1 तो आउटपुट 61 होगा क्योंकि सबसेट है -

{33, 18, 10}

एल्गोरिदम

हम एक प्रीसम ऐरे बनाते हैं, जिसमें प्रत्येक इंडेक्स में दिए गए ऐरे में 'इंडेक्स' से 'इंडेक्स + K' तक के सभी तत्वों का योग होता है। और सम ऐरे का आकार n+1-k होगा
अब यदि हम आकार k के सबएरे को शामिल करते हैं, तो हम उस सबएरे के किसी भी तत्व को किसी अन्य सबएरे में फिर से शामिल नहीं कर सकते क्योंकि यह ओवरलैपिंग सबएरे बनाएगा। इसलिए हम शामिल सबएरे के k तत्वों को बाहर करके रिकर्सिव कॉल करते हैं
यदि हम एक सबएरे को बाहर करते हैं तो हम उस सबएरे के अगले k-1 तत्वों का उपयोग अन्य सबएरे में कर सकते हैं इसलिए हम उस सबएरे के केवल पहले तत्व को बाहर करके रिकर्सिव कॉल करेंगे।
अंत में max(शामिल योग, बाहर किया गया योग) वापस करें

उदाहरण

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