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

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.

• Hint: First prove that there is always an optimal solution with a very simple structure. Commented Nov 16, 2020 at 20:28
• (A way to do this is to consider an arbitrary solution that does not have this structure, and show that by moving it "towards" this structure, you never make the solution worse. It follows that repeated steps will eventually get you to a solution with the structure, and it will be no worse than what you started with.) Commented Nov 16, 2020 at 20:31
• I understand that that is the approach. Still, I fail to see how the proceed. Can you give me a possible construction? Commented Nov 16, 2020 at 22:28
• What simple structure did you decide on? Commented Nov 16, 2020 at 23:48
• How about pre-computing the $\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 best(p,q) = best way of having $q$ intervals such that we end at $[p-x,p]$ for some $x \geq 0$. Our goal is to find best(n,r) and backtrack to find the intervals. best(p,q) = min(best(p,q-1), max(best(p-1,q-1),dist(p-1,p)), max(best(p-2,q-1), dist(p-2,p)), $\cdots$)) where dist(x,y) = $\Sigma_{i=x}^{y} a_i$ which is pre-computed. This probably works but the backtracking seems difficult. Commented Nov 17, 2020 at 8:35

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.

• Binary search $\text{ans}$ over the interval $\left[\frac{\sum a_i}{n}, \sum a_i \right]$. And when we have $\leq r$ intervals while greedy searching, then it is NOT necessarily possible to divide it into $r$ intervals such that $f(r,X) \leq \text{ ans}$. Take $r=3, S = \{2,3,1,5,7\}$. When $\text{ans}=8$, we have $(2+3+1+5,7+6)$ form the initial intervals. Then we need to break it such that 7,6 gets separated. It isn't possible to break into intervals such that each sum is $\leq \text{ ans}$. Commented Dec 3, 2020 at 5:45
• As for the "breaking", we can use break[x][y] that returns the proper break in O(1) or we can use something similar to Kadane's algorithm to compute the break in O(N). But pre computing this saves time. Commented Dec 3, 2020 at 5:46
• @oldsailorpopoye Greedy must work (why? because each interval in the greedy has sum $\leq ans$, since we create a new interval if the sum would become greater than $ans$). For your example, we would get $(2,3,1)$,$(5)$,$(7)$,$(6)$. Since we have 4 intervals, we can't divide into 3 intervals, so $f(r,X) > 8$. Commented Dec 3, 2020 at 9:31
• @oldsailorpopoye At the end, greedy will produce a division into $\leq r$ intervals s.t. each interval has sum $\leq f(r,X)$ where $f(r,X)$ is the answer found from binary search. We can transform this into a solution with exactly $r$ intervals by splitting some of the intervals up (can be done arbitrarily). Commented Dec 3, 2020 at 9:32
• I misunderstood your solution in that case. I was treating $\text{ans}$ as the upper bound instead of answer and the resulting ans will be the min of all these ans for which we get a proper partitioning into $r$ intervals. Yours is a neater approach now that I realize it. Commented Dec 4, 2020 at 2:08