C++ में उपसर्ग योग का उपयोग करते हुए O(n) में अधिकतम सबअरे योग

समस्या कथन

सकारात्मक और नकारात्मक पूर्णांकों की एक सरणी को देखते हुए, उस सरणी में अधिकतम सबअरे योग ज्ञात करें

उदाहरण

यदि इनपुट ऐरे − {-12, -5, 4, -1, -7, 1, 8, -3} है तो आउटपुट 9

एल्गोरिदम

• इनपुट सरणी के उपसर्ग योग की गणना करें।

• प्रारंभ करें− min_prefix_sum =0, रेस =-अनंत

• i =0 से n के लिए एक लूप बनाए रखें। (एन इनपुट सरणी का आकार है)।

  • कैंड =प्रीफ़िक्स_सम [i] - मिनी

  • अगर कैंड रेस से बड़ा है (अब तक का अधिकतम सबरे योग), फिर कैंड द्वारा रेस अपडेट करें।

  • अगर prefix_sum[i] min_prefix_sum (अब तक का न्यूनतम उपसर्ग योग) से कम है, तो prefix_sum[i] द्वारा updatemin_prefix_sum.

• रिटर्न रेस

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int maximumSumSubarray(int *arr, int n){
   int minPrefixSum = 0;
   int res = numeric_limits<int>::min();
   int prefixSum[n];
   prefixSum[0] = arr[0];
   for (int i = 1; i < n; i++) {
      prefixSum[i] = prefixSum[i - 1] + arr[i];
   }
   for (int i = 0; i < n; i++) {
      res = max(res, prefixSum[i] - minPrefixSum);
      minPrefixSum = min(minPrefixSum, prefixSum[i]);
   }
   return res;
}
int main(){
   int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Result = " << maximumSumSubarray(arr, n) <<endl;
   return 0;
}

आउटपुट

जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -

Result = 9