Return to Answer

You need to place two cuts. I recommend placing the right cut first, then the left, because it's easier to ignore the end of an array than the beginning. So, for every right cut (roughly n possibilities), partition the remaining left array into two halves (O(log n) using a binary search). That's O(n log n).

#include <algorithm>
#include <iostream>
#include <limits>
template <typename T>
T minimaxPartition2(const T cumulative[], size_t len) {
 T total = cumulative[len - 1];
 T ideal = total / 2;
 const T *split = std::upper_bound(cumulative, cumulative + len, ideal);
 return std::min(
 std::max(*(split - 1), total - *(split - 1)),
 std::max(*split, total - *split)
 );
}
template <typename T>
T minimaxPartition3(const T cumulative[], size_t len) {
 using std::min;
 using std::max;
 T total = cumulative[len - 1];
 T best = std::numeric_limits<T>::max();
 for (size_t rSplit = len - 1; rSplit >= 1; rSplit--) {
 T rightSum = total - cumulative[rSplit - 1];
 best = min(best, max(rightSum, minimaxPartition2(cumulative, rSplit)));
 }
 return best;
}
int main() {
 size_t len;
 std::cin >> len;
 long cumulative[len];
 for (int sum = 0, i = 0; i < len; sum = cumulative[i++]) {
 long n;
 std::cin >> n;
 if (n <= 0) {
 return 1;
 }
 cumulative[i] = sum + n;
 }
 std::cout << minimaxPartition3(cumulative, len) << std::endl;
 return 0;
}

Further improvement should be possible. You should be able to drastically reduce the hunting for the right cut using a heuristic, since the partition should yield a right sum that is close to 1/3 of the total.

I suggest the following strategy:

1. Tentatively place the right split past the end of the array, and find the optimal left split. (Given the cumulative representation, partitioning an array optimally into two is easy — O(log n) using a binary search for half of the total.)
2. Move the right split to the left, and adjust the left split as necessary. (The optimal left split can only ever move left, if at all.)

The complexity of the algorithm is O(n).

#include <algorithm>
#include <iostream>
#include <iterator>
template <typename T>
T max(const T a, const T b, const T c) {
 return std::max(a, std::max(b, c));
}
/**
 * Given an array represented as cumulative sums, find a split
 * that produces the most equal left and right sums.
 */
template <typename ConstIter>
ConstIter minimaxPartition2(ConstIter begin, ConstIter end) {
 typedef typename std::iterator_traits<ConstIter>::value_type T;
 if (end - begin <= 1) {
 return end;
 }
 T total = *(end - 1);
 T ideal = total / 2;
 ConstIter split = std::upper_bound(begin, end, ideal);
 T aSum = std::max(*(split - 1), total - *(split - 1));
 T bSum = std::max(*split, total - *split);
 return aSum < bSum ? split - 1 : split;
}
/**
 * Given an array represented as cumulative sums, find a split
 * that produces the most equal left and right sums by considering
 * small leftward movements of the upperEstimate split point.
 */
template <typename ConstIter>
ConstIter minimaxPartition2(ConstIter begin, ConstIter end, ConstIter upperEstimate) {
 typedef typename std::iterator_traits<ConstIter>::value_type T;
 const T total = *(end - 1);
  ConstIter bestSplit = upperEstimate;
 T bestSum = std::max(*(bestSplit - 1), total - *(bestSplit - 1));
 for (ConstIter split = bestSplit - 1; split >= begin; --split) {
 T sum = std::max(*(split - 1), total - *(split - 1));
 if (sum < bestSum) {
 bestSum = sum;
 bestSplit = split;
 } else {
 break;
 }
 }
 return bestSplit;
}
template <typename ConstIter>
typename std::iterator_traits<ConstIter>::value_type
minimaxPartition3(ConstIter begin, ConstIter end) {
 typedef typename std::iterator_traits<ConstIter>::value_type T;
 const T total = *(end - 1);
 ConstIter split2 = end,
  split1 = minimaxPartition2(begin, split2);
  T leftSum = *split1,
 rightSum = 0,
  best = max(leftSum, total - leftSum - rightSum, rightSum);
  while (--split2 > split1 && rightSum < best) {
 rightSum = total - *split2;
  split1 = minimaxPartition2(begin, split2, split1);
 leftSum = *split1;
 best = std::min(best, max(leftSum, total - leftSum - rightSum, rightSum));
 }
 return best;
}
int main() {
 size_t len;
 std::cin >> len;
 long cumulative[len];
 for (int sum = 0, i = 0; i < len; sum = cumulative[i++]) {
 long n;
 std::cin >> n;
 if (n <= 0) {
 return 1;
 }
 cumulative[i] = sum + n;
 }
 std::cout << minimaxPartition3(cumulative, cumulative + len) << std::endl;
 return 0;
}