# 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 <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;
}

• Which version of C++ are you using? Feb 13, 2015 at 14:55
• Feb 13, 2015 at 14:56
• I don't see how the algorithm qualifies as dynamic-programming, so I've removed the tag. Feb 13, 2015 at 18:13
• Deleting a question after you have received an answer would be the worst possible insult to those who have volunteered the time to read, answer, and vote on your question. That is absolutely not allowed. Feb 13, 2015 at 22:53
• @D.W. But every question on CR also allows answers that criticize other aspects of the code, so the questions are not redundant. Feb 13, 2015 at 23:54

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).

• Can you rewrite it for older C++ versions (no auto variables, etc.)? It seems quite a bit complicated and arrays are better in time complexity than vectors, I think...
– user65079
Feb 27, 2015 at 15:40
• Great! Thank you very much!!! However, the algorithm looks quite simple... Are you sure it doesn't miss any case? Do you have any "hints" of a possible proof?
– user65079
Feb 27, 2015 at 16:37
• Something is wrong: in {5, 6, 1, 4, 9, 3, 1, 2} it outputs 14, whereas the correct is 13: { {5, 6, 1}, {4, 9}, {3, 1, 2} }...
– user65079
Feb 27, 2015 at 17:17
• @Jason: You have right, my algorithm is wrong :-( I will think if there is a fix which is still in O(n), else there is a solution in O(n log(n))... Feb 27, 2015 at 18:01
• Any update yet?
– user65079
Mar 3, 2015 at 20:39

Yes, more efficient algorithms do exist.

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

1. 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.

2. 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
...

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


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.

• I suggest the following: copy-paste your answer to this thread so that I can erase this thread and we have all the answers gathered there. (Note: there are 3 totally different techniques of solution until now)
– user65079
Feb 13, 2015 at 18:50
• @Jason You created this mess by cross-posting the question. Please don't trouble users further by asking answers to be duplicated as well. Feb 13, 2015 at 22:43

## Code organization

main() does everything. It would be a good idea to separate the concerns, such that main() is responsible for I/O and for calling a function that determines the optimal partition.

## Variables

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


Those are some weird variable names! If you have some sticky keys on your keyboard, you should clean out the residue.

new int[n];


If you call new, there should be a corresponding delete[]. Better, you could use a variable-length array or a std::vector<int>.

## Data representation

A useful observation to make is that you don't need to store the individual numbers. Rather, the running total is more useful. The benefit is that you can find the sum of any subarray in constant time. That is, instead of storing

2, 80, 50, 42, 1, 1, 1, 2

you should store

2, 82, 132, 174, 175, 176, 177, 179

You could always reconstruct the original list from the running totals (not that you need to do so to solve this problem).

The only concern would be overflow. You didn't specify any length or size constraints on your problem, though, so I'm not going to worry about it.

## Algorithm

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;
}

• std::max(a, std::max(b, c)); may be replaced by std::max({a, b, c}); in C++11. Feb 16, 2015 at 18:38