配点: 600 点
問題文
长度为 N 序列 A = \left( a_1, a_2, \ldots, a_N \right) 。 如果输入
将这个序列分成几个连续的非空子序列 考虑分成 B_1, B_2, \ldots, B_K 。例如, 拆分A = (5, -3, 6, 2, 4) 时,A 的示例如下:
- B_1 = (5), B_2 = (-3, 6, 2), B_3 = (4)
- B_1 = (5, -3), B_2 = (6, 2, 4)
- B_1 = (5, -3, 6, 2, 4)
部分列 B_i 的 分数 S \left( B_i \right) 的,B_i 中包含的项的最大值和最小值之间的差异 将其定义为 \max B_i - \min B_i 。
A 最优划分时子序列的得分总和 找到 \sum_i S \left( B_i \right) 的最大值。
制約
- 所有输入均以整数形式给出
- 1 \leq N \leq 200{,}000
- |a_i| \leq 10^{9} (1 \leq i \leq N)
入力
输入是按以下格式从标准输入给出的。
N a_1 a_2 \ldots a_N
出力
请输出子序列分数之和的最大值。
入力例 1
9 1 2 2 4 5 2 3 4 1
出力例 1
9
B_1 = (1, 2, 2, 4), B_2 = (5, 2, 3), B_3 = (4, 1) 是最佳分区之一。
- S(B_1) = 4 - 1 = 3
- S(B_2) = 5 - 2 = 3
- S(B_3) = 4 - 1 = 3
,所以总和是 9 就是答案。
入力例 2
12 3 -1 4 1 5 -9 2 6 5 -3 5 9
出力例 2
37