Minimize $f(r,X)$ over all sets $X$ using Dynamic Programming

Question

If a set of numbers $a_1, a_2, \cdots, a_n$ $($such that each $a_i \in \mathbb{N} \cup \{0\})$ and an $r \in \mathbb{N}$ are given, find set $X = \{x_0, x_1, \cdots, x_r \ | \ x_0 = 0 < x_1 < \cdots < x_r = n\}$ such that $f(r,X) := \displaystyle\max_{j=0}^{r-1} \sum_{i = x_j}^{x_{j+1}-1} a_i$ is minimized over all possible $X$.

---

I can think of a brute force approach, that is, generate $\Theta ({{n-1} \choose {r-1}})$ sets $X$ and calculate the $\max$ for each $X$, each of which takes as many as $r$ steps. This is a very inefficient approach. How do I make it better? I feel like there is a way using DP. (Please feel free to edit the title if this is not DP).

This seems like a possible solution. What if we pre-compute $\displaystyle\Sigma_{i=j}^{j+k} {a_i}$ $(k \geq 0)$ for all $1 \leq j \leq n$ first and then create a DP with function $$\text{best}(p,q) = \text{best way of having } q \text{ intervals such that we end at } [p-x,p] \text{ for some } x \geq 0$$ Our goal is to find $\text{best}(n,r)$ and backtrack to find the intervals.

$\text{best}(p,q) = \min \{ \text{best}(p,q-1), \ \max(\text{best}(p-1,q-1), \text{dist}(p-1,p)), \ \max(\text{best}(p-2,q-1), \text{dist}(p-2,p)), \dots) \}$

where $\text{dist}(x,y)$ = $\displaystyle\Sigma_{i=x}^{y} a_i$ which is pre-computed. This probably works but the backtracking seems difficult and time-hungry.

I tried greedy and I could generate counter-examples right away. Was not very helpful.

Answer 1

Main idea: Instead of finding $X$ itself, find the minimum value for $f(r,X)$. After you do this, it is easy to find a minimal $X$. Simply greedily add elements to an interval until the sum of the interval is too large - once this happens, create a new interval at that position.

Finding the minimal value for $f(r,X)$ is a classic (maybe prototypical) binary search problem. The algorithm is as follows: binary search over the answer. Within your binary search, greedily add elements to an interval until the sum of the interval is higher than the answer - once this happens, create a new interval. (Note that this is the same method as is used to construct $X$.) At the end, check how many intervals you have formed - if it is $\leq r$ then it is possible to divide the array into $r$ intervals such that $f(r,X) \leq ans$. The time complexity is $O(NlogS)$, where $S$ is the sum of all $a_i$.

Although binary search does work for all practical values, your statement does state $\mathbb{N}$ as the possible size of elements. If elements can be arbitrarily large, we can use DP as you mentioned, fairly similar to the DP that you use. $best(p,q)$ can be the minimum $f(\cdot)$ taking $q$ intervals from the first $p$ elements. By transitioning in the same way as your statement, we get a trivial $O(N^3)$ solution.

We can also optimise this DP. One optimisation: $best(x,q)$ is monotonically increasing as $x$ increases, but $dist(x,p)$ is monotonically decreasing. So, we can use binary search to find the intersection of the two lines. The transition is now $O(logN)$ and the overall complexity is $O(N^2logN)$.

Important thing to note: this DP avoids the issues with your DP because it doesn't store the actual $X$ within the DP itself.