Fast solution for a combinatorial maximizaton problem
You seem to be looking for the optimal single-deletion-correcting code of length n. As far as I know, it's an open problem.

This paper states that


The Varshamov-Tenengolts code (specifically $VT_0$) is a good candidate, but there has been no proof of this as of yet. It is the set of all words for which $\sum_{i=0}^{n} i\cdot x_i \equiv 0 \mod n+1$ where $x_i$ is the $i$-th digit in $x$'s binary representation. Its size can be computed as $$\frac{1}{2(n+1)}\sum_{d\mid n+1 \land 2\not \mid d} \phi(d)2^\frac{n+1}{d}$$. The first few values of the above formula can be found at A000016.
The above code has been proven to be optimal for small values of $n$, and to be asymptotically optimal for large $n$.
No efficient algorithm has been found to generate/check the optimal code. The largest value of $n$ for which an optimal code is known (and confirmed to be the above) is $9$ (actually $10$).