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.