CF484D Kindergarten

在一所幼儿园中，老师正在将孩子们分组。老师让孩子们排成一行，并为每位孩子指定了一个整数“魅力值”。每个孩子必须恰好属于一个小组。每个小组必须是这行中连续的、非空的一段孩子。一个小组的“社交力”定义为组内任意两位孩子的魅力值之差的最大值（特别地，如果一个小组中只包含一位孩子，则它的社交力为 $0$）。 老师想要以某种方式将孩子们分成若干组，使得所有小组社交力的总和最大。请你帮他求出最大的总社交力是多少。

第一行包含一个整数 $n$，表示队伍中的孩子人数（$1\le n\le 10^6$）。 第二行包含 $n$ 个整数 $a_i$，表示第 $i$ 位孩子的魅力值（$-10^9\le a_i\le 10^9$）。

输出所有小组最大可能的社交力总和。

在第一个样例中，一种可能的划分方式是：前三个孩子形成一个组，其社交力为 $2$，剩下的两个孩子形成一个组，其社交力为 $1$。 在第二个样例中，无论如何分组，每个小组的社交力都为 $0$。 由 ChatGPT 5 翻译