A partition algorithm for positive integers

I have encountered the following problem that I found very interesting to solve:


Given an array of positive integers {a1, a2, ..., an} you are required
to partition the array into 3 blocks/partitions such that the maximum
of sums of integers in each partition is the minimum it can be.
Restriction: you cannot alter the turn in which the numbers appear
(example: if you have {2, 5, 80, 1, 200, 80, 8000, 90} one partition
CANNOT be the {2, 80, 1, 90}). The program must output ONLY the maximum sum, not the partitions.

So, for example let's have the array:

{2, 80, 50, 42, 1, 1, 1, 2}

The best partitioning according to the problem is:

{ {2, 80}, {50}, {42, 1, 1, 1, 2} }

so the output of the program in this case would be 82.

I have already thought of a \$O(n^2)\$ algorithm, but isn't there any better (e.g. \$O(n)\$ or \$O(n\log n)\$) algorithm?

My \$O(n^2)\$ algorithm:

#include   
#include   

using namespace std;  

int main() {  

    int n, *arr, onee = 0, twoo, threee, total = 0, maxx = -1, temp_maxx;

    cin >> n;
    arr = new int[n];

    for (int i = 0; i > arr[i];
        total += arr[i];
    }

    // O(n^2) is the following

    for (int i = 1; i < n - 1; i++) {
        onee += arr[i - 1];
        twoo = 0;
        for (int j = i + 1; j < n; j++) {
            twoo += arr[j - 1];
            threee = total - twoo - onee;
            temp_maxx = max(max(onee, twoo), threee);
            if ((temp_maxx < maxx) || (maxx == -1))
                maxx = temp_maxx;
        }
    }

    cout << maxx;

    return 0;
}

Yes, more efficient algorithms do exist.

\$O(n*\log(n))\$:

-
Let's fix the end of the first part. Now we are interested in finding the end of the second one. I claim that we need to check only two candidates: the last index such that the sum of the second part is not greater then the sum of the third part and the one immediately after it (I will not post a formal proof here, but intuitively it is clear that we want keep these two sums as close to each other as possible.

-
To do it in efficient manner, we can use a binary search and prefix sums:

// Returns the sum of the [left, right] subarray in O(1) time.
int getSum(int left, int right)
    // Prefix sums are used here.
    ...

// Checks if the current answer is better than the current best
// and makes appropriate updates. 
void updateAnswer(int firstEnd, int secondEnd)
    ...

// Corner cases are ignored here.
// This piece of code just represents an idea of the algorithm, it can 
// contain bugs.
for (int first  1)
        int mid = (low + high) / 2
        if (getSum(first + 1, mid) <= getSum(mid + 1, n - 1))
            low = mid
        else
            high = mid
    updateAnswer(first, low)
    updateAnswer(first, low + 1)

Now we can use the following observation: when the first variable increases in the code above, the low value either increases or stays the same, too. That's why we can apply two pointers technique and get an \$O(n)\$ time complexity.

StackExchange Code Review Q#80442, answer score: 3