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 $\ \le\ \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\ge 2\ $ we get
$$ n+2\ \le\ U(n)\ \le u(n)\ \le\ \big\lceil\frac{3\cdot n}2\big\rceil + 1 $$
We see from (i)+(ii) that finding $\ u(n)\ $ got reduced to a finite computation.