解题思路与算法

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

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

题目内容

$TK$ 有一个长度为n的整数数组{ $a_1,a_2,...,a_n$ };

小 $O$ 希望将这些元素分成三份，要求每个元素恰好属于其中一份，且三份元素个数都相同;