#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <utility>

int MaxSum(int lo, int hi, const int* arr)
{
    if (lo > hi)
    {
        return 0;
    }
    if (lo == hi)
    {
        return arr[lo];
    }

    int mid = (lo + hi) / 2;

    int maxLeft = 0;
    int maxRight = 0;

    int sum = 0;

    for (int i = mid; i >= lo; --i)
    {
        sum += arr[i];
        if (sum > maxLeft)
        {
            maxLeft = sum;
        }
    }

    sum = 0;
    for (int i = mid + 1; i <= hi; ++i)
    {
        sum += arr[i];
        if (sum > maxRight)
        {
            maxRight = sum;
        }
    }

    int MaxCrossing = maxLeft + maxRight;

    int maxInA = MaxSum(0, mid, arr);
    int maxInB = MaxSum(mid + 1, hi, arr);

    return std::max(MaxCrossing, std::max(maxInA, maxInB));
}

void test(const std::pair<std::vector<int>, int> & seq)
{
    int result = MaxSum(0, seq.first.size() - 1, seq.first.data());
    std::cout << "Expected " << seq.second << ", got " << result << '\n';
}

int main()
{
    std::vector<std::pair<std::vector<int>, int>> sequences =
    {
        { { -10, 11, 10, -10, 2, 3, -6, 1 }, 21 },
        { { -10, 11, 10, -3, 8, 3, 4, -6, 1 }, 33 },
    };

    for (auto& sequence : sequences)
        test(sequence);
}