Envío 2170

Código

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int max_across(int a[], int left, int mid, int right) {
    int sum = 0;
    int left_result = INT_MIN;
    for (int i = left; i <= mid; i++)
    {
        sum = sum + a[i];
        if (sum > left_result) {
            left_result = sum;
        }
    }
    sum = 0;
    int right_result = INT_MIN;
    for (int i = mid+1; i <= right; i++)
    {
        sum = sum + a[i];
        if (sum > right_result) {
            right_result = sum;
        }
    }
    int max1 = max(left_result, left_result + right_result);
    return max(max1, right_result);
}

int solve(int a[], int left, int right) {
    if(left == right) {
        return a[left];
    }
    int midPoint = (right + left)/2;
    int max_left = solve(a, left, midPoint);
    int max_right = solve(a, midPoint + 1, right);
    int max_crossing = max_across(a, left, midPoint, right);
    int max_border = max(max_left, max_right);
    return max(max_border, max_crossing);
}

int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int best = solve(a, 0, n-1);
    cout << best << endl;
    return 0;
}