I couldn't write any algorithm that can do this in good order for $a_i < 100$ and $n < 2000$ :(
how we can partition $a_1, a_2, a_3, ... a_n$ in two sequence X and Y such that $|X_1 - X_2| + |X_2 - X_3| + ... + |X_{m - 1} + X_m| + |Y_1 - Y_2| + |Y_2 - Y_3| + ... + |Y_{t - 1} + Y_t|$ being minimum?
Please help me please sorry for my bad English :(
You can see that whatever the final sequences are, it is optimal only if both are in ascending or descending order. It is kinda easy to show that. Let $X_l, X_m,X_n$ be the terms of any of the final two sequences in order. It can be seen that the value when they are out of order will be greater than when they are in order.
Now once they are in order we can see that the $|X_1 - X_2| + |X_2 - X_3| + ... + |X_{m - 1} + X_m| + |Y_1 - Y_2| + |Y_2 - Y_3| + ... + |Y_{t - 1} + Y_t|$ can be replaced by $|X_m - X_1| + |Y_t - Y_1|$ i.e. the quantity depends only on the final and first terms in each sequence.
Now how do we get the maximum sum out of the two series. By splitting the initial sorted sequence along the largest gap. So let $|Z_1 - Z_2| , |Z_2 - Z_3| , ... , |Z_{k - 1} + Z_k|$ be the gaps on the undivided sorted sequence. Find out which of the gaps is the largest . Then create the two sequences such that that gap vanishes.