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 <stdio.h>  #include <iostream>  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 < n; i++) {        cin >> 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;}
A partition algorithm for positive integers
c++;algorithm;c++11;complexity
Edit:Previous algorithm failed, redo the algorithm completely.Start with a full mid part, and distribute its values to its best neighbor until it is not the greatest part:unsigned int get_min_partition3_value(const std::vector<unsigned int>& v){    const unsigned int total_sum = std::accumulate(v.begin(), v.end(), 0u);    auto it1 = v.begin();    auto it2 = v.end();    unsigned int part1 = 0;    unsigned int part2 = total_sum;    unsigned int part3 = 0;    unsigned int res = part2;    while (part1 < part2 && part3 < part2) {        res = part2; // part2 is greater than part1 and part3        if (part1 + *it1 < part3 + *(it2 - 1)) {            part1 += *it1;            part2 -= *it1;            ++it1;        } else {            --it2;            part3 += *it2;            part2 -= *it2;        }    }    res = std::min(res, std::max(part1, part3));    return res;}Live demo.(For C++03, replace auto by std::vector<unsigned int>::const_iterator)Complexity is O(n).Previous not working live example.