Prefix sum problems: Maximum equilibrium sum in an array

Problem Statement:

Given an array, you need to find the maximum value of prefix sum which is also suffix sum for index i in arr[]

Example:

Input: arr[] = {-1, 4, 5, 0, 5, 4, -1}
Output: 8

Explanation: Prefix sum of arr[0, 1, 2, 3] = suffix sum of arr[3, 4, 5, 6]

Solution Explanation:

Take 2 temp array

calculate prefix sum to store subarray from [0 to i]
calculate suffix sum to store subarray from [i to n-1]

Then check if prefix[i] == suffix[i] and also compare with overall max result so far and return the result.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;


int solution(vector<int>& nums) 
{
    int n = nums.size();
    
    vector<int> prefixSum(n);

    vector<int> suffixSum(n);

    int result = INT_MIN;

    prefixSum[0] = nums[0];

    for (int i = 1; i < n; i++) 
        prefixSum[i] = prefixSum[i - 1] + nums[i]; 

    suffixSum[n - 1] = nums[n - 1];
    
    if (prefixSum[n - 1] == suffixSum[n - 1])
        result = max(result, prefixSum[n - 1]);
        
    for (int i = n - 2; i >= 0; i--) 
    {
        suffixSum[i] = suffixSum[i + 1] + nums[i];
        if (suffixSum[i] == prefixSum[i]) 
            result = max(result, prefixSum[i]);     
    }

    return result;
}


int main()
{
    vector<int> arr =  {-1, 4, 5, 0, 5, 4, -1};
  
    cout << solution(arr)<<endl;
    
    return 0;
}

Output

8