← 返回题目列表

AtCoder · codequeen2023_final_e

E. 良好的分区

中文机器翻译题面 查看原题

配点: 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