分数: 366 分
问题陈述
高桥负责美术馆的展览策划。对于即将到来的展览,他决定对作品进行策略性的安排,以便给参观者留下深刻的印象。
展会有 N 艺术品,每件编号为 1 to N。每件艺术品 i 有一个“音调值” A_i,它是艺术品色调亮度的数值表示。
高桥计划将艺术品单排展示。为了最大限度地提高对参观者的影响,他认为相邻艺术品之间的色调值差异越大,对比度就越突出,从而创造出更令人印象深刻的展览。
具体来说,当 N 艺术品排成一行,“影响值”定义为所有相邻艺术品对之间色调值绝对差的总和。也就是说,对于每个位置 1-st 到 (N-1)-th,计算该位置的图稿与下一个位置的图稿之间色调值的绝对差值,这些值的总和就是影响值。
看在高桥的份上,找到当艺术品排列成影响力值最大时的最大影响力值。
约束
- 1 \leq N \leq 10^6
- 1 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表艺术品数量。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表每件作品的色调值。
输出
在单行中输出最大影响值。
示例输入 1
4 1 3 8 10
示例输出 1
23
示例输入 2
5 7 7 7 7 7
示例输出 2
0
示例输入 3
10 12 45 3 89 34 21 76 55 8 100
示例输出 3
563
示例输入 4
30 42 1000000000 17 500000000 999999937 123456789 987654321 314159265 271828182 1 750000000 250000000 600000001 399999999 888888888 111111111 222222222 777777777 333333333 666666666 444444444 555555555 135791357 246802468 975318642 864209753 1024 2048 4096 8192
示例输出 4
18117750936
示例输入 5
1 1000000000
示例输出 5
0