C++ में दी गई राशि से कम या उसके बराबर राशि वाले अधिकतम योग उप-सरणी

इस समस्या में, हमें एक सरणी और एक योग दिया जाता है। हमारा काम एक ऐसा प्रोग्राम बनाना है जो c++ में दिए गए योगों से कम या उसके बराबर राशि वाले अधिकतम योग उप-सरणी को खोजेगा।

हमें n से कम या उसके बराबर किसी भी लंबाई का उप-सरणी ज्ञात करना है जिसका योग दिए गए योग से कम या उसके बराबर है।

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

इनपुट - सरणी ={3, 5, 1, 8, 2, 9}, योग =25

आउटपुट -25

स्पष्टीकरण - 25 से कम या उसके बराबर योग वाली उप-सरणी हैं {5, 1, 8, 2, 9}

अधिकतम योग उप-सरणी को खोजने का एक सरल तरीका है, सरणी पर पुनरावृति करना और सभी उप-सरणी का योग ज्ञात करना और फिर निकटतम या समान योग का पता लगाना। लेकिन इस विधि में O(n*n) की समय जटिलता होगी क्योंकि दो लूप की आवश्यकता होती है।

स्लाइडिंग विंडो . का उपयोग करके इस समस्या को हल करने का एक अधिक कुशल तरीका है तरीका। जिसमें हम अधिकतम योग के साथ वर्तमान योग की जांच करेंगे और तुलना के आधार पर विंडो में तत्वों को जोड़ या घटाएंगे।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,

#include <iostream>
using namespace std;
int findMax(int a, int b){
   if(a>b)
      return a;
   return b;
}
int maxSumsubarray(int arr[], int n, int maxSum){
   int sum = arr[0], overallMax = 0, start = 0;
   for (int i = 1; i < n; i++) {
      if (sum <= maxSum)
      overallMax = findMax(overallMax, sum);
      while (sum + arr[i] > maxSum && start < i) {
         sum -= arr[start];
         start++;
      }
      sum += arr[i];
   }
   if (sum <= maxSum)
      overallMax = findMax(overallMax, sum);
   return overallMax;
}
int main(){
   int arr[] = {3, 1, 4, 7, 2, 9, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 20;
   cout<<"The maximum sum of subarray with sum less than or equal to "<<sum<<" is "<<maxSumsubarray(arr, n, sum);
   return 0;
}

आउटपुट

The maximum sum of subarray with sum less than or equal to 20 is 18