AtCoder Beginner Contest 125 D - Flipping Signs

atcoder.jp

問題概要

整数の要素N個をもつ配列Aがある。
この中の隣り合う要素2つを選んで符号を反転させる操作を好きなだけ繰り返し、sum(A)を最大にしたい。

制約
2 ≤ N ≤ 10^5

• 10^9 ≤ Ai ≤ 10^9

解法

2つの要素の符号が同時に変わるので、何度操作を行っても負の要素の数を2で割ったあまりは不変である。
よって負の要素の個数の奇偶で場合分けする。
1° 偶数の場合
要素全てを正にできる。つまりAの各要素の絶対値の和を取れば答え。
2° 奇数の場合
一つの要素だけ負、残りは全部正にできる。なのでAの要素で絶対値が最小のものを負にして、残りは全部正にすればいい。

N = int(input())
A = sorted(list(map(int,input().split())))
t = 0
for e in A:
    if e < 0:
        t += 1
B = sorted([abs(e) for e in A])

if t%2 == 1:
    print(sum(B)-B[0]*2)
else:
    print(sum(B))