In 1972, I have developed a general theory of isometric embeddings of finite metric spaces into finite-dimensional Banach spaces, in particular, the injective case, i.e. into metrically injective spaces $\mathbb R^n$ with metrics given by $\max$. An announcement has appeared a couple of years later in AMS Notices. One of the theorems fits the present thread:
For every natural $k, n$, there is an EXPLICIT natural constant $\mu(k, n)$ such that the following two statements are equivalent:
(i) every $k$-element metric space can be isometrically embedded into $\mathbb R^n$ with the distance given by $\max$;
(ii) every $k$-element metric space with integer distances and of diameter ${\leq} \mu(k, n)$ can be isometrically embedded into subspace $\{0, \ldots, \mu(k, n)\}^n$ of $\mathbb R^n$ with the distance given by $\max$.
For each natural $n$, there exists a maximal $u(n)=k$ as above; and also $U(n)$ similar to $u(n)$ but for ALL $n$-dimensional Banach spaces TOGETHER (for each fixed dimension $n$). Then in the non-trivial case of $n \geq 2$ we get
$$ n+2 \leq u(n) \leq U(n) \leq \left\lceil\frac{3\cdot n}2\right\rceil + 1 $$
We see from (i)+(ii) that finding $u(n)$ has been reduced to a finite computation.
