C++ में ऐरे में अधिकतम संतुलन योग

समस्या कथन

एक ऐरे arr[] दिया गया है। इंडेक्स i के लिए arr[] में अधिकतम प्रीफिक्स योग का मान ढूंढें जो सफिक्स योग भी हो।

उदाहरण

यदि इनपुट ऐरे है -

Arr[] = {1, 2, 3, 5, 3, 2, 1} तो आउटपुट 11 है -

• प्रीफिक्स योग = arr[0..3] = 1 + 2 + 3 + 5 = 11 और
• सफिक्स योग = arr[3..6] = 5 + 3 + 2 + 1 = 11

एल्गोरिदम

• ऐरे को ट्रैवर्स करें और प्रत्येक इंडेक्स के लिए प्रीफिक्स योग को ऐरे presum[] में स्टोर करें, जिसमें presum[i] सबऐरे arr[0..i] का योग स्टोर करता है
• ऐरे को फिर से ट्रैवर्स करें और सफिक्स योग को दूसरे ऐरे suffsum[] में स्टोर करें, जिसमें suffsum[i] सबऐरे arr[i..n-1] का योग स्टोर करता है
• प्रत्येक इंडेक्स के लिए जांचें कि क्या presum[i], suffsum[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