A problem in discrete optimization

I order the points $x_1<\ldots<x_n$ in this answer.

Your assumption for the minimization is correct. (In fact, if the points are distinct, left-to-right and right-to-left are the only two traversals of minimal length.)

Proof: Given any path which goes through all the points, the portion of its route which starts at one of $x_1$ or $x_n$ will have length at least equal to the distance $|x_1-x_n|$, by the triangle inequality. But the direct linear route you describe has exactly this distance, so it must be optimal.

In the maximization case, things are somewhat more complicated, but the sort of "zigzag" procedure you describe is optimal.

If $n$ is even, then we create a path by connecting $x_i$ to $x_{n+1-i}$ and $x_{n-i}$ for $1\le i<n/2$. We also connect $x_{n/2}$ to $x_n$. This creates a path between all nodes, which I claim is maximal.

If $n=2k+1$ is odd, then we create a path by connecting $x_i$ to $x_{n+1-i}$ and $x_{n-i}$ for $1\le i<k$. We also connect $x_{k}$ to $x_n$. I claim that either this path or its reflection by flipping our indexing of each $x_i$ and performing the same procedure is optimal, depending on whether $x_{k+1}-x_{k}$ or $x_{k+2}-x_{k+1}$ is larger (with the reflection being optimal if the former is larger).

To see why this is true, we count, for each segment between adjacent points in our interval, the number of times we walk across that segment. The total length of our path is just the sum, over each segment, of its length times the number of times we traverse it. The segment from $x_i$ to $x_{i+1}$ can be traversed at most $2i$ times, since we can only go back and forth once each from every one of the $i$ nodes left of it. By the same argument on the other side, the segment can be traversed at most $2(n+1-i)$ times.

Additionally, no segment can be traversed more than $n-1$ times, since there are only $n-1$ segments total, and if any segment is traversed that often, it is unique.

So, for example, if $n=7$ then the number of traversals of each of the 6 segments is bounded above by either $2,4,5,6,4,2$ or $2,4,6,5,4,2$. If $n=8$ it is bounded by $2,4,6,7,6,4,2$.

Then, to see that this path is maximal, we just observe that the described path traces over every segment a maximal number of times, so it is impossible to walk a longer path than they trace out.

Edit: I have included a diagram for $n=8$, to make the idea a little clearer. Above each segment between adjacent points is the number of times the path traverses that segment.

enter image description here