解题思路与算法

数学推导

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

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

1. 取一份为最大和 $S_{\text{top}}$：此时值为

题目内容

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

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

记第$i$份的元素和为 $W_i(i= 1, 2, 3)$;

请你计算表达式$|w1-w2|+|w2-w3|$的最大可能值。

输入描述

第一行输入一个整数$n(3≦n≦2×10^5)$，表示数组大小，题目保证$n$是$3$的倍数;

第二行输入$n$个整数$a_1,a_2，...,a_n (1≦a_i≦10^9)$,表示数组元素。

输出描述

输出一个整数，表示最大值$|w1- w2|+|w2-w3|$

样例1

输入

3
1 2 3

输出

3

说明

在这个样例中，将每个元素单独成组，得到三个元素和分别为$1,2,3$，将它们编号为$w_1= 3, w_2= 1, w_3=2$,可得$|w1 - w2|+|w2- w3|=2+1=3$。