A partition algorithm

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

Given an array of positive integers $\{a_1, a_2, ..., a_n\}$ 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 $\mathcal{O}(n^2)$ algorithm, but isn't there any better ( e.g. $\mathcal{O}(n)$ or $\mathcal{O}(n \log n)$ ) algorithm?

My $\mathcal{O}(n^2)$ algorithm is (it is pseudocode):

1. input $n \in \mathbb{Z}$
2. Let $m \leftarrow -1$
3. Let $r_1 \leftarrow r_2 \leftarrow r_3 \leftarrow 0$
4. Let $A \leftarrow (a_0,...,a_{n-1})$
5. Let $S \leftarrow \sum_{i=0}^{n-1}{a_i}$
6. for each $i = 1$ until $n-2$ do
7. $\quad r_1 \leftarrow (r_1 + a_{i-1})$
8. $\quad r_2 \leftarrow 0$
9. $\quad$ for each $j = (i+1)$ until $n-1$ do
10. $\quad\quad r_2 \leftarrow (r_2 + a_{j-1})$
11. $\quad\quad r_3 \leftarrow S - (r_2 + r_1)$
12. $\quad\quad \max_{\mathsf{temp}} \leftarrow \max(\max(r_1,r_2),r_3)$
13. $\quad\quad$if $(\max_{\mathsf{temp}} < m \, \vee m = -1)$ then
14. $\quad\quad\quad m \leftarrow \max_{\mathsf{temp}}$
15. $\quad\quad$endif
16. return $m$
• @SpencerWieczorek Posted it there too but I want a brand new algorithm, not someone to check the above – Jason Feb 13 '15 at 14:46
• Please don't crosspost on different SE sites simultaneously! Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration or repost. It may be prudent to include links in either direction and explain why the particular perspective of the other site seems useful. – Raphael Feb 13 '15 at 16:12
• What is the value of $a_{-1}$ in your pseudo-code (first iteration of outer loop) ? – babou Feb 13 '15 at 17:34
• Cross-posted on CodeReview.SE and on StackOverflow. This violates site rules. No, cross-posting on 3 sites and then deleting 2 of them later after you get answers is not allowed either. – D.W. Feb 13 '15 at 21:11

Since you find it interesting to solve, I do not want to completely spoil it too much for you. So here is a big hint to solve it in linear time.

You start with two indices $i$ and $j$ which are the first and last indices of central segment.

Initially you set $i=0$ and $j=n$. And you compute the 3 sums in $s_1$, $s_2$ and $s_3$. So initially $s_1=s_3=0$.

Then you progressively increase $i$ and decrease $j$, by variations of 1, keeping $s_1$ and $s_3$ about the same value (by doing the change on the smallest sum $s_1$ or $s_3$), until one becomes bigger than $s_2$. Each increment or decrement takes constant time (adding or substracting the value of an element to two of the sums, and doing a few comparisons).

When one of $s_1$ and $s_3$ becomes larger than $s_2$, say for example $s_1$. Then you have $s_1\geq s_2 > s_3$.

Then you know that the right value for $i$ is either the current value or the previous value. Typically it is the previous value of i, if $s_1$ has become greater that the previous value of $s_2$. But things are a bit more subtle. So you note this value of $s_1$ as $m_1$, a possibility for the maximum, and then try to see if you could have achieved a lower value for the maximum with the previous value of $i$ and $s_1$, just before the last increase. So you revert $i$ to that previous value, and you start to decrease $j$ to get the lowest possible maximum for $s_2$ and $s_3$ without touching $i$ (that is easy, and recall that $s_1$ remains lower than both others sums). Let $m_{2,3}$ be the lowest maximum found. Now, if $m_{2,3}$ is greater than $m_1$, then the answer is $m_1$, else the answer is $m_{2,3}$.

And you must consider the symmetrical case when $s_3$ is the first to exceed $s_2$.

• So, we are using a two-pointer approach. Just I didn't much understand the last part: the "fiddling with the limits". Moreover, what to do if somehow we encounter s1==s2 or s3==s2? – Jason Feb 13 '15 at 18:38
• When $s_1$ or $s3$ becomes greater than $s_2$, then you know that the current values for $i$ and $j$ are nearly optimal. But You then need a little bit of case analysis to get precisely the best choice for them. Sometimes, if you have a bunch of very small elements, you may have to choose where they go. But the algorithm stays linear. I did not develop all details. This should be faster (about twice as fast) than the first algorithm given on stackoverflow. I did not read the second one. – babou Feb 14 '15 at 0:05
• @Jason I updated the answer. You have it all. It is obviously linear, and explores only about 2/3rd of indices on average for the boundaries between partitions. BTW, why the tag dynamic programming? - - - - Please clean up by deleting your 2 previous comments. – babou Feb 14 '15 at 21:05
• I thought it could have a DP solution, but not... So, I cleaned comments and tags up. But can you explain why from the reverted i, there is a need to decrease j? So, the algorithm is approximately 2*n because we have two loops - the normal and for the reverted. – Jason Feb 15 '15 at 7:26
• Actually, constants do not mean much in asymptotic complexity, i.e. $O(2n)=O(n)$. But, if you want to analyze the loops, you see that indices are used at most once, by $i$ or by $j$. The second loop looks at indices not used by the first. So it can count as a single loop. There is no decrease of sums in the secong loop, but just the fact that $j$ has to progress by decreasing in both loops. It may be that you can save some operations on each step with a cumulative sum array suggested by Jarod42. This would require precise counting. It might be a bit better in average complexity. – babou Feb 15 '15 at 8:24