分数: 400 点
问题陈述
有 N 整数, A_1, A_2, ..., A_N,按此顺序排成一行。
您可以对此整数序列执行以下操作任意次:
操作: 选择一个整数 i 满意 1 \leq i \leq N-1。两者相乘 A_i 和 A_{i+1} by -1.
让 B_1, B_2, ..., B_N 是运算后的整数序列。
找到最大可能值 B_1 + B_2 + ... + B_N.
约束
- 输入中的所有值都是整数。
- 2 \leq N \leq 10^5
- -10^9 \leq A_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N A_1 A_2 ... A_N
输出
打印最大可能值 B_1 + B_2 + ... + B_N.
示例输入 1
3 -10 5 -4
示例输出 1
19
如果我们执行如下操作:
- 选择 1 as i,将序列更改为 10, -5, -4.
- 选择 2 as i,将序列更改为 10, 5, 4.
我们有 B_1 = 10, B_2 = 5, B_3 = 4。这里的总和, B_1 + B_2 + B_3 = 10 + 5 + 4 = 19是最大可能的结果。
示例输入 2
5 10 -4 -8 -11 3
示例输出 2
30
示例输入 3
11 -1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000
示例输出 3
10000000000
输出可能不适合 32- 位整数类型。