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):
- input $n \in \mathbb{Z}$
- Let $m \leftarrow -1$
- Let $r_1 \leftarrow r_2 \leftarrow r_3 \leftarrow 0$
- Let $A \leftarrow (a_0,...,a_{n-1})$
- Let $S \leftarrow \sum_{i=0}^{n-1}{a_i}$
- for each $i = 1$ until $n-2$ do
- $\quad r_1 \leftarrow (r_1 + a_{i-1})$
- $\quad r_2 \leftarrow 0$
- $\quad$ for each $j = (i+1)$ until $n-1$ do
- $\quad\quad r_2 \leftarrow (r_2 + a_{j-1})$
- $\quad\quad r_3 \leftarrow S - (r_2 + r_1)$
- $\quad\quad \max_{\mathsf{temp}} \leftarrow \max(\max(r_1,r_2),r_3)$
- $\quad\quad$if $(\max_{\mathsf{temp}} < m \, \vee m = -1)$ then
- $\quad\quad\quad m \leftarrow \max_{\mathsf{temp}}$
- $\quad\quad$endif
- return $m$