Find maximum distance between elements given constraints on some
What you describe is a linear program. You can use the following formulation:

Let $x_i$ be the $i$th element. The variables are $d_1,\ldots, d_{n-1}$, where $d_i$ denotes difference between $x_{i+1}$ and $x_i$. You require $d_i\ge 0$.

If two elements $x_i,x_j$ should be at least within some distance $\ell^-_{ij}$, then you set
$$ d_i+d_{i+1}+\cdots +d_{j-1} \le \ell^-_{ij}.$$
If they should be at least $\ell^+_{ij}$ away from each other you set
$$ d_i+d_{i+1}+\cdots +d_{j-1}  \ge \ell^+_{ij}.$$
Then maximize the objective function $\sum_{i=1}^{n-1} d_i$. An LP solver can also tell you if the problem is infeasible or unbounded. Of course you could look for a faster solution for this special class of LPs.