समस्या कथन
सकारात्मक और नकारात्मक पूर्णांकों का एक सरणी दिया गया है, उस सरणी में अधिकतम सबएरे सम ज्ञात करें।
उदाहरण
यदि इनपुट सरणी है {-12, -5, 4, -1, -7, 1, 8, -3} तो आउटपुट 9 होगा।
एल्गोरिदम
इनपुट सरणी का प्रीफिक्स सम निकालें।
प्रारंभ करें: min_prefix_sum = 0, res = -infinite
i = 0 से n तक लूप बनाए रखें (n इनपुट सरणी का आकार है)।
cand = prefix_sum[i] – min_prefix_sum
यदि cand res (अब तक का अधिकतम सबएरे सम) से अधिक है, तो res को cand से अपडेट करें।
यदि prefix_sum[i], min_prefix_sum (अब तक का न्यूनतम प्रीफिक्स सम) से कम है, तो min_prefix_sum को prefix_sum[i] से अपडेट करें।
res वापस करें।
उदाहरण
#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