分数: 700 点
问题陈述
给你一个长度-N 序列 A = (A_1, A_2, \ldots, A_N).
您将重复执行以下操作,直到序列的长度达到最大 1:选择两个相邻的数字并将它们从序列中删除。
一次操作获得的分数是两个所选数字的绝对差。
找出可能获得的最大总分。
约束
- 2 \le N \le 3 \times 10^5
- 1 \le A_i \le 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印获得的最大可能总分。
示例输入 1
4 1 2 5 3
示例输出 1
5
首先,删除 A_2 和 A_3。得到的分数是 |A_2 - A_3| = 3.
接下来,删除 A_1 和 A_4。请注意,由于之前的操作,这两个数字现在相邻。得到的分数是 |A_1 - A_4| = 2.
因此,获得的总分是 5.
总分不可能达到 6 或更大,因此打印 5.
示例输入 2
7 3 1 4 1 5 9 2
示例输出 2
14
示例输入 3
5 1 1 1 1 1
示例输出 3
0