Given a sequence of $2 \leq n \leq 50$ numbers $s = (s_1,s_2,...,s_n)$, find a permutation $a = (a_1,a_2,...,a_n)$ of $s$ such that $$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$$ is maximized.

I found many codes that get "Accepted" in the online judge with the following greedy algorithm.

If $n = 2$, then $a = s$. Stop the algorithm.

Let $s' = (s'_1,s'_2,...,s'_n)$ be $s$ in the non decreasing order. Start the optimal sequence with $a = (s'_1,s'_n)$ and remove these two elements from $s'$.

$\text{loop}$: Let $s' = (s'_1,s'_2,...,s'_k)$ be the remaining sorted sequence. If $k = 0$, stop the algorithm. If $k > 0$, from the following choices, choose the one that yields the greatest absolute difference.

1. Remove $s'_1$ from $s'$ and push it to the front of $a$.
2. Remove $s'_1$ from $s'$ and push it to the back of $a$.
3. Remove $s'_k$ from $s'$ and push it to the front of $a$.
4. Remove $s'_k$ from $s'$ and push it to the back of $a$.

Go to $\text{loop}$.

I'm having trouble to formally prove the correctness of this algorithm.

For example, to prove the optimal substructure property. Let $b = (b_1,b_2,...,b_n)$ be an optimal solution. How can I argue that $(b_1,b_2,...,b_{n-1})$ is also optimal? What if it's not???

And for proving the greedy-choice property. Let $a = (a_1,a_2,...,a_m)$ be a partial, yet still optimal, solution. The algorithm relies on the fact that only adding $s'_1$ or $s'_k$ to $a$ can yield another optimal solution. Why is this true? And more, why we don't need to test inner positions, but only the ends?

Any help with these proofs? Or, perhaps, this algorithm is not correct? But I can't find a counterexample...

Given a sequence of $2 \leq n \leq 50$ numbers $s = (s_1,s_2,...,s_n)$, find a permutation $a = (a_1,a_2,...,a_n)$ of $s$ such that $$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$$ is maximized.

I found many codes that get "Accepted" in the online judge with the following greedy algorithm.

If $n = 2$, then $a = s$. Stop the algorithm.

Let $s' = (s'_1,s'_2,...,s'_n)$ be $s$ in the non decreasing order. Start the optimal sequence with $a = (s'_1,s'_n)$ and remove these two elements from $s'$.

$\text{loop}$: Let $s' = (s'_1,s'_2,...,s'_k)$ be the remaining sorted sequence. If $k = 0$, stop the algorithm. If $k > 0$, from the following choices, choose the one that yields the greatest absolute difference.

1. Remove $s'_1$ from $s'$ and push it to the front of $a$.
2. Remove $s'_1$ from $s'$ and push it to the back of $a$.
3. Remove $s'_k$ from $s'$ and push it to the front of $a$.
4. Remove $s'_k$ from $s'$ and push it to the back of $a$.

Go to $\text{loop}$.

I'm having trouble to formally prove the correctness of this algorithm.

For example, to prove the optimal substructure property. Let $b = (b_1,b_2,...,b_n)$ be an optimal solution. How can I argue that $(b_1,b_2,...,b_{n-1})$ is also optimal? What if it's not???

And for proving the greedy-choice property. Let $a = (a_1,a_2,...,a_m)$ be a partial, yet still optimal, solution. The algorithm relies on the fact that only adding $s'_1$ or $s'_k$ to $a$ can yield another optimal solution. Why is this true? And more, why we don't need to test inner positions for inserting the new element, but only the ends?

Any help with these proofs? Or, perhaps, this algorithm is not correct? But I can't find a counterexample...