C++ में आकार k के उपसरणी का अधिकतम (या न्यूनतम) योग ढूंढें

इस समस्या में, हमें एक सरणी arr[] और एक संख्या k दी गई है। हमारा कार्य आकार k के उपसरणी का अधिकतम (या न्यूनतम) योग ढूंढना है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट: arr[] = {55, 43, 12, 76, 89, 25, 99} , k = 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