समस्या कथन
एक सरणी को देखते हुए []। उपसर्ग योग का अधिकतम मान ज्ञात करें जो कि गिरफ्तारी में अनुक्रमणिका i के लिए प्रत्यय योग भी है []।
उदाहरण
यदि इनपुट ऐरे है -
Arr[] ={1, 2, 3, 5, 3, 2, 1} तो आउटपुट 11 है -
- उपसर्ग योग =गिरफ्तारी[0..3] =1 + 2 + 3 + 5 =11 और
- प्रत्यय योग =गिरफ्तारी[3..6] =5 + 3 + 2 + 1 =11
एल्गोरिदम
- सरणी को पार करें और सरणी प्रीसम में प्रत्येक इंडेक्स के लिए प्रीफ़िक्स योग को स्टोर करें [], जिसमें प्रीसम [i] सबएरे एआर का योग संग्रहीत करता है [0..i]
- सरणी को फिर से पार करें और प्रत्यय योग को किसी अन्य सरणी प्रत्यय [] में संग्रहीत करें, जिसमें प्रत्यय [i] उप-सरणी गिरफ्तारी का योग संग्रहीत करता है [i..n-1]
- प्रत्येक सूचकांक के लिए जाँच करें कि क्या अनुमान [i] प्रत्यय के बराबर है [i] और यदि वे समान हैं तो तुलना करें, अब तक के कुल अधिकतम के साथ मूल्य की तुलना करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
int preSum[n];
int suffSum[n];
int result = INT_MIN;
preSum[0] = arr[0];
for (int i = 1; i < n; ++i) {
preSum[i] = preSum[i - 1] + arr[i];
}
suffSum[n - 1] = arr[n - 1];
if (preSum[n - 1] == suffSum[n - 1]) {
result = max(result, preSum[n - 1]);
}
for (int i = n - 2; i >= 0; --i) {
suffSum[i] = suffSum[i + 1] + arr[i];
if (suffSum[i] == preSum[i]) {
result = max(result, preSum[i]);
}
}
return result;
}
int main() {
int arr[] = {1, 2, 3, 5, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max equlibrium sum = " << getMaxSum(arr, n) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Max equlibrium sum = 11