[算法][面试题]疯狂队列-排列使序列两两间差绝对值总和最大

题目

对于一个给定的数列A，其相邻两项差值的绝对值被称作“疯狂值”。现要求对数列进行任意排列，以使得该数列整体所具有的“疯狂值”达到最大，并输出这一最大值。

样例

当队列的排列顺序为25-10-40-5-25时，各相邻成员之间身高差的绝对值之和等于15+30+35+20=100。此数值为该排列方式下的总和，而实际中存在多种不同的排列组合方式可达到相同结果。

题解

首发于此：https://blog.nowcoder.net/n/aee5c4e3c14f48eeb678c6f839a6369b

显而易见，最终的排列方式必定呈现交错分布，且遵循[...低 高 低 高...]的结构；
1.因此，首先对序列进行升序排列，可以直观地看出较高数值的部分对应于数组的后半段，较低数值的部分则位于数组的前半段。
2.分析[...低1, 高1, 低2, 高2...]这样的模式可知，相邻元素之间的绝对差值之和等于(高1-低1)+(高1-低2)+(高2-低2)…
3.假设数组包含无限多项，则显然较高数值的那一半中的每个元素都会被计算两次，而较低数值的那一半中的每个元素则会被减去两次。
4.然而实际情况下数组项数必然是有限的，因此必定存在一个中断点。这个中断点必然出现在升序排列后的数组中间位置：

• 4.1 若总项