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?

This problem is slightly misleading in that one might wonder how to use the condition that the number of points to choose from is the square of the number of chosen points. That is actually a distraction.

Here comes an hint:


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.

This problem can indeed be solved by dynamic programming efficiently. In case when the previous hint is not enough, here are the subproblems stated explicitly.


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

StackExchange Computer Science Q#70904, answer score: 2