Flipping Signs

题目描述

有 $N$ 个整数，$A_1, A_2, ..., A_N$，按此顺序排列在一行。 你可以对该整数序列执行以下操作任意次： 操作：选择满足 $1 \leq i \leq N-1$ 的整数 $i$。将 $A_i$ 和 $A_{i+1}$ 同时乘以 $-1$。 令 $B_1, B_2, ..., B_N$ 为你执行操作后的整数序列。 求 $B_1 + B_2 + ... + B_N$ 的最大可能值。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $A_2$ $...$ $A_N$

输出格式

输出 $B_1 + B_2 + ... + B_N$ 的最大可能值。

3
-10 5 -4

19

5
10 -4 -8 -11 3

30

11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000

10000000000

提示

输入中的所有数值均为整数。 $2 \leq N \leq 10^5$ $-10^9 \leq A_i \leq 10^9$如果我们按如下方式执行操作：

选择 $1$ 作为 $i$，序列变为 $10, -5, -4$。 选择 $2$ 作为 $i$，序列变为 $10, 5, 4$。

此时 $B_1 = 10, B_2 = 5, B_3 = 4$。这里的和 $B_1 + B_2 + B_3 = 10 + 5 + 4 = 19$ 是最大可能的结果。
输出可能无法适应 32 位整数类型。

标签: AtCoder|abc125D

来源

AtCoder|abc125D