ABC 125 D - Flipping Signs - Yoshichiの日記

問題概要

N個の数列Aに対して、任意(i < N)のiとi+1に対して-1を乗算し
数列Bを作成する。作成したsum(数列B)が最大となる値を答えよ。

解法(解説AC)

正負判定を行い、負の値が偶数個の場合全て正の値にすることが可能。
負の数が奇数個の場合、任意の値を1つだけ負の値にすることが可能。
なので、負の値が偶数個の場合、すべての値を正にした状態でsum(B)。
負の値が奇数個の場合、abs(A)の中で最も小さい値を負の値にしてsum(B)を取ればよい。

提出コード

n = int(input())
a = list(map(int, input().split()))

count = 0
s = 0
b = []
for i in range(n):
    count += 1 if a[i] < 0 else 0
    b.append(abs(a[i]))
flg = False
if count % 2 == 1:
    flg = True
ans = sum(b)
if flg:
    ans -= min(b) * 2
print(ans)