解题思路与算法

给定长度为 $n$ 的数组，需将其划分为大小均为 $\tfrac n3$ 的三份，记三份的元素和为 $w_1,w_2,w_3$ 。目标是最大化： $|w_1 - w_2| + |w_2 - w_3|.$

由于三份无序、标签可调，我们可以证明最优方案只会把一份设为“中间”和一份设为极端，从而推导出两种候选值：

题目内容

教练收到了一份包含 $n$ 名学员的能力值清单，每名学员对应一个正整数。他需要将所有学员恰好分成三个小队，每个小队的人数必须相等。对于一支小队，其总能力值等于队内所有学员能力值之和。记三支小队的总能力值分别为 $X, Y, Z$ 。教练希望最大化以下表达式的值：

|X - Y| + |Y - Z|

请你帮助教练求出这个最大值。

约束条件：学员总数 $n$ 满足 $3 \le n \le 2 \times 10^5$ 且为 $3$ 的倍数。每名学员的能力值为一个整数，范围在 $[1, 10^9]$ 。