#include <iostream>
#include<vector>
#include<climits>
using namespace std;

vector<int> bestprefixArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> p1(n);

    int bestEnding = nums[0];
    int bestSoFar = nums[0];

    p1[0] = nums[0];

    for (int i = 1; i < n; i++) {
        bestEnding = max(nums[i], bestEnding + nums[i]);
        bestSoFar = max(bestSoFar, bestEnding);
        p1[i] = bestSoFar;
    }

    return p1;
}

vector<int> bestSuffixArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> s1(n);

    int bestEnding = nums[n - 1];
    int bestSoFar = nums[n - 1];

    s1[n - 1] = nums[n - 1];

    for (int i = n - 2; i >= 0; i--) {
        bestEnding = max(nums[i], bestEnding + nums[i]);
        bestSoFar = max(bestSoFar, bestEnding);
        s1[i] = bestSoFar;
    }

    return s1;
}

int main() {
	vector<int> nums={0,6,5,-20,2,5,1,9,4};
    int n = nums.size();

    vector<int> p1 = bestprefixArray(nums);
    vector<int> s1 = bestSuffixArray(nums);

    int ans = INT_MIN;

    for (int i = 0; i < n - 1; i++) {
    ans = max(ans, p1[i] + s1[i + 1]);
    }
	
	cout<<ans<<endl;
	
    return 0;
}