# Finding a partition with minimum “maximal length”

We're given $n^2$ different points in $(0,1)$ : $x_1< x_2 < \dots < x_{n^2}$.

We are required to choose $n$ points $x_{i_1}<\dots<x_{i_n}$ such that the value of $\max\,\{x_{i_1}, x_{i_2}-x_{i_1}, x_{i_3}-x_{i_2},\dots,x_{i_n} - x_{i_{n-1}}, 1-x_{i_n}\}$ is minimal.

It feels a lot like a dynamic programming problem, but I didn't manage to divide it into appropriate subproblems.

Any ideas?

• Keep trying! The only way to learn is to solve problems. – Yuval Filmus Feb 27 '17 at 13:28
• Just to make clear: there is indeed a way to solve it using dynamic programming. – Yuval Filmus Feb 27 '17 at 13:43
• What did you try? What subproblems did you already try? We have some material on how to systematically solve dynamic programming problems here: cs.stackexchange.com/tags/dynamic-programming/info. Please review the material in those links, try some more, and if you're still stuck, edit the question to show what you've tried and what progress you've made. – D.W. Feb 27 '17 at 20:28

How about instead of $n^2$, you are given some $m$ different numbers where $m\geq n$? This more general problem is not in any way harder then the original question.
Can you compute the following function of integer $w$ and $k$, where $1\leq k \leq w$? $$m(w,k) := \min_{i_0 = 0,\,i_k = w,\,i_1\lt\cdots<i_k} \max\{x_{i_1} - x_{i_0},\,x_{i_2}-x_{i_1},\,\cdots,\,x_{i_k} - x_{i_{k-1}}\}$$ What is the technique? We replace the last item $1-x_{i_n}$ with $x_k - x_{i_{k-1}}$. We can compute subproblem $m(w,k)$ from subproblems $m(w',k-1)$ with $w'<w$. The original problem is just the special case $m(n^2+1, n+1)$ if we set $x_{n^2+1} = 1$.