← 返回题目列表

AtCoder · abc125_d

D. 翻转标志

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

分数: 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- 位整数类型。