A dynamic programming approach would be:
$f (p, k)$ is the minimum size when we considered prefix $\{x_1, x_2, \ldots, x_p\}$, and selected exactly $k$ items from it, the last one being $x_p$.
We add sentinels $x_0 = 0$ and $x_{n^2 + 1} = 1$ for our comfort.
Base: $f (0, 0) = 0$.
Transitions: $f (p, k) = \min\limits_{q = 1, 2, \ldots, p - 1} \max \left\{f (q, k - 1), x_p - x_q\right\}$.
Answer: $f (n^2 + 1, n + 1)$, the point number $n + 1$ being the added value $x_{n^2 + 1} = 1$.
In total, this takes $O(n^2)$ to calculate a single $f (p, k)$, and there are $O (n^3)$ such values, so the approach will take $O(n^5)$ time and $O(n^3)$ memory.
The memory could be reduced to $O(n^2)$ by calculating iteratively, like:
for k = 1, 2, ..., n+1:
for p = 1, 2, ..., n^2 + 1:
calculate f (p, k)
And storing $f (p, k)$ only for the current and the previous values of $k$ at every moment: the storage strategy can be to store $f (p, k)$ in f[p][k mod 2].
The time could be perhaps reduced to $O(n^3)$ by altering the function to optimize the $O (n^2)$ transition cost to something like $O (1)$ amortized.
But instead, let us consider another approach.
Say we want the answer to be at most $s$.
We can then greedily construct a subset.
First, let $x_{i_1}$ be the greatest possible: $i_1 = \max i : x_i \le s$.
Next, let $x_{i_2}$ be the greatest possible: $i_2 = \max i: x_i - x_{i_1} \le s$.
Then define $i_3 = \max i: x_i - x_{i_2} \le s$, and so on.
If this leads to $x_{i_n}$ such that $1 - x_{i_n} > s$, the answer can't be $s$.
Otherwise, we just constructed a subset of $\le n$ elements with the answer at most $s$.
As the value $i$ is always increasing, for a given fixed value $s$, the check whether $s$ can be the answer takes $O (n^2)$ time and $O (1)$ additional memory.
What's left is to run a binary search over the value $s$, and for each candidate $s$, execute the greedy algorithm above.
The number of binary search iterations can be $\log n$ (there are $O (n^4)$ possible candidates for $s$), or $\log C$ where $C$ is the required precision.
For example, if all $x_i$ are integers from $0$ to $L$, we have a binary search over integers from $0$ to $L \cdot n^2$, so it will complete in $O (\log (L \cdot n^2))$.
In total, this approach takes $O (n^2 \log n)$ or $O (n^2 \log C)$, which is better than an optimized dynamic programming approach would achieve.
