#include <bits/stdc++.h>
using namespace std;

int main() 
{
    // index     1   2  3   4  5
     int b[5] = {5,-3,-5,15,5};
     int n=5;

    int maxPrefixSum[5];
    int maxSuffixSum[5];

    // current = 0
    // maxPrefixSum = 0
    //Initially both the current and maxPrefixSum will be zero 
    //     5     =  max( 5 ,  0   +   5)
    //  current = max(b[i] , current + b[i])
    //               5         = max(  5    ,     5 )
    //maxPrefixSum[i] = max(maxPrefixSum[i-1] , current)
    
    int current = b[0];
    maxPrefixSum[0] = b[0];
    for(int i=1; i<n; i++)
    {
        current = max(b[i] , current + b[i]);
        maxPrefixSum[i] = max(maxPrefixSum[i-1] , current);
    }

    // current = 0
    //maxSuffixSum = 0
    //     15  =    max( 15,       0  +  15)
    //current = max(b[i] , current + b[i]);
    //           20                = max(   15+5  ,  15)
    //maxSuffixSum[i] = max(maxSuffixSum[i+1] , current);
    current = b[n-1];
    maxSuffixSum[n-1] = b[n-1];
    for(int i=n-2; i>=0; i--)
    {
        current = max(b[i] , current + b[i]);
        maxSuffixSum[i] = max(maxSuffixSum[i+1] , current);
    }

    
    int maxSum = INT_MIN;
    for(int i=1; i<n-1; i++)
    {
        //     25        = max(     0          ,        5                     +           20)
        maxSum = max(maxSum , maxPrefixSum[i] + maxSuffixSum[i+1]);
    }

    cout<<"Max sum of two nonoverlapping subarrays: "<<maxSum; // o/p -> 25
}