Optimal Partition of Book Chapters Suppose you want to read a book with $n$ chapters, and chapter $i$ has $a_i$ pages. Now you want to read the entire book in $d$ days. But there are two restrictions:


by the end of each day, you cannot be in the middle of a chapter.
You must read the chapters in order.


You also want to minimize the maximum number of pages read in a single day.

Now let's consider the brute force algorithm: look at every possible way of dividing the chapters into $d$ days, and compute the maximum number of pages read in a single day. There are $\binom{n+d-1}{n}$ ways to divide the chapters up (using stars and bars) and you must check the number of pages read in each day, ultimately by doing $n$ operations. So this algorithm takes $O\left(n\binom{n+d-1}n\right)$ time, which is pretty bad, but I can't think of how to improve it.

Imagine an analogous decision problem:


  Given a book with $n$ chapters, is it possible to read it in $d$ days such that you never read more than $k$ pages in a single day without violating the restrictions?


The decision problem seems to have a really easy greedy solution: Each day, read as many chapters as you can without exceeding $k$ pages. If you're done with the book after $d$ days, the answer is yes. Otherwise, the answer is no. This takes $O(n)$ time.

It seems weird that the decision problem would have such a simple solution but the original one doesn't. Can anyone think of how to do better than the brute force algorithm for the original problem?
Your brute force solution is far from optimal. One improvement is to use dynamic programming. For every $i,j$, determine the minimal maximum number of pages per day when reading the first $i$ chapters in $j$ days. Implemented naively, this leads to an $O(n^2d)$ solution, though you might be able to improve this to $O(nd)$ using a smart implementation.

A perhaps better solution is to use binary search. You state that it is easy to determine whether a certain maximum number of pages can be achieved. To find the minimum number that can be achieved, use binary search with the decision algorithm as an oracle. The running time in principle depends on the total number of pages, but in fact there are only $n^2$ different possible answers, and this leads to an $O(n^2)$ algorithm, which can probably be improved to $O(n\log n)$ with some additional ideas.