求数组的最长路径和问题

Question

假设有一个大小为N的数组

L = [1, 2, ..., n]

随机选择两个值, 两者的差的绝对值就是它们之间的路径长

比如, 选择到了1 和 n 这两个值, 那么路径长就是n-1

依次选择下去, 直到每一个数都被选到,
(假设这个数组的大小是偶数吧, 那就不会出现有单独的不能两两配对的情况了)

现在, 问题是, 怎么选择, 才能使得得到的路径长的和最大呢?

Answer 1

S = [1, 2, ..., n/2]
B = [n/2+1, n/2+2, ...,n]

每次分别在上述两个区间取值，则路径长之和最大。

Result = Sum(B) - Sum(S)
　　　 = n*n/4

Answer 2

先从小到大排序，得到a1,a2,...,an,其中a1<=a2<=...<=an，最大和就是(a[n]-a[1])+(a[n-1]-a[2])+...+(a[n/2]-a[n/2-1])，也就是后一半的和减去前一半的和，不知题意理解是否正确？

Answer 3

最大的一半减去最小的一半