Problem:


Score : 400 points

Problem Statement

There are N integers, A_1, A_2, ..., A_N, arranged in a row in this order.

You can perform the following operation on this integer sequence any number of times:

Operation: Choose an integer i satisfying 1 \leq i \leq N-1. Multiply both A_i and A_{i+1} by -1.

Let B_1, B_2, ..., B_N be the integer sequence after your operations.

Find the maximum possible value of B_1 + B_2 + ... + B_N.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

-10^9 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible value of B_1 + B_2 + ... + B_N.

Sample Input 1

3
-10 5 -4

Sample Output 1

19

If we perform the operation as follows:

Choose 1 as i, which changes the sequence to 10, -5, -4.

Choose 2 as i, which changes the sequence to 10, 5, 4.

we have B_1 = 10, B_2 = 5, B_3 = 4. The sum here, B_1 + B_2 + B_3 = 10 + 5 + 4 = 19, is the maximum possible result.

Sample Input 2

5
10 -4 -8 -11 3

Sample Output 2

30

Sample Input 3

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

Sample Output 3

10000000000

The output may not fit into a 32-bit integer type.



Sample input:
3
-10 5 -4


Sample output:
19

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n = int(input())
a = list(myinput())
b = list(map(abs,a))

ind = b.index(min(b))

c = deepcopy(a)
# print(c)
i = 0
while i<(ind):
    s = c[i]
    t = c[i+1]
    if s>=0 and t>=0:
        i += 2
    elif s>=0 and t<=0:
        i += 1
    elif s<=0 and t>=0:
        c[i] = -1*s
        c[i+1] = -1*t
        i += 1
    elif s<=0 and t<=0:
        c[i] = -1*s
        c[i+1] = -1*t
        i += 2
# print(c)
d = c[::-1]
# print(d)
i = 0
while i<(n-ind-1):
    s = d[i]
    t = d[i+1]
    if s>=0 and t>=0:
        i += 2
    elif s>=0 and t<=0:
        i += 1
    elif s<=0 and t>=0:
        d[i] = -1*s
        d[i+1] = -1*t
        i += 1
    elif s<=0 and t<=0:
        d[i] = -1*s
        d[i+1] = -1*t
        i += 2
# print(d)

ans = sum(d)
print(ans)

Submission status: Accepted

Solution code:
# D - Flipping Signs

n = int(input())
a = list(int(x) for x in input().split())

cntMinus = 0
ans = 0
minAbs = 10**10
for i in range(n):
    if a[i]<0:
        cntMinus += 1
    absi = abs(a[i])
    minAbs = min(minAbs, absi)
    ans += absi

if cntMinus%2==0:
    print(ans)
else:
    print(ans-minAbs*2)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = []
cnt = 0
for i in range(n):
    b.append(abs(a[i]))
    if a[i] < 0:
        cnt += 1
if cnt%2 == 1:
    print(sum(b)-2*min(b))
else:
    print(sum(b))

Submission status: Accepted

Solution code:
N = int(input())

A = list(map(int, input().split()))

total = 0
minus = 0

l = []
for i in range(N):
  total += abs(A[i])
  l.append(abs(A[i]))
  if A[i] < 0:
    minus += 1

ans = total
if minus % 2 == 1:
  ans = total - 2 * min(l)

print(ans)

Submission status: Accepted

Solution code:
n  = int(input())
a = list(map(int,input().split()))
ans = 0
mn = 0
for i in range(n):
    if a[i] < 0:
        mn += 1
        a[i] = abs(a[i])
    ans += a[i]
if 0 in a or mn%2 == 0:
    print(ans)
else:
    print(ans - 2*min(a))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
total = 0
minimum = 1000000000
for n in range(N):
    if A[n] > 0:
        total += A[n]
        minimum = min(minimum, A[n])
    else:
        total += -A[n]
        minimum = min(minimum, -A[n])
        count += 1
if count%2 == 0:
    print(total)
else:
    print(total-2*minimum)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=[]
p=[]
s=0
c=0
for i in range(n):
    s+=abs(a[i])
    if a[i]<0:
        c+=1
        c%=2
        m.append(a[i])
    else:p.append(a[i])
if c==0:print(s)
else:
    m.sort()
    if len(p)==0:
        print(s+2*m[-1])
        exit()
    p.sort()
    if abs(m[-1])>abs(p[0]):print(s+m[-1]-p[0]-m[-1]-p[0])
    else:print(s+m[-1]*2)

Submission status: Accepted

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

sum=0
min=10**9
minus=0
for i in a:
  if i>=0:
    sum=sum+i
    if min>i:
      min=i
  else:
    minus=minus+1
    sum=sum-i
    if min>-i:
      min=-i
print(sum if minus%2==0 else sum-min*2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = list(map(abs, A))
    minus = 0
    for i in range(N):
        if A[i]<0:
            minus += 1
    if minus%2==0:
        ans = sum(B)
    else:
        ans = sum(B) - min(B)*2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    s = sum(abs(a) for a in A)
    if sum(1 for i in A if i < 0) & 1:
        s -= 2 * min(abs(a) for a in A)
    return s

print(main())

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    negatives = 0
    zeros = 0
    min_abs = 10**9 + 1
    for a in A:
        if a < 0:
            negatives += 1
        if a == 0:
            zeros += 1
        min_abs = min(min_abs, abs(a))
    ans = sum(map(abs, A))
    if negatives % 2 == 0 or zeros != 0:
        print(ans)
        return

    ans -= 2*min_abs
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    negatives = 0
    zeros = 0
    min_abs = 10**9 + 1
    for a in A:
        if a < 0:
            negatives += 1
        if a == zeros:
            zeros += 1
        min_abs = min(min_abs, abs(a))
    ans = sum(map(abs, A))
    if negatives % 2 == 0 or zeros != 0:
        print(ans)
        return

    ans -= 2*min_abs
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = 0
f = 0
for i in range(n):
    if a[i] == 0:
        b = 1
    else:
        if a[i] < 0:
            f += 1
    a[i] = abs(a[i])
m = min(a)
if b == 1 or f % 2 == 0:
    ans = sum(a)
else:
    ans = sum(a) - 2*m
print(ans)

Submission status: Accepted

Solution code:
_, *a = map(int, open(0).read().split())
*z, = map(abs, a)
s = sum(z)
print(s if len([i for i in a if i<0])%2==0 or 0 in a else s-min(z)*2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
cnt = 0
ans = [abs(i) for i in a]
s = sum(ans)
mm = min(ans)

for i in a:
  if i < 0:
    cnt += 1

if mm == 0 or cnt%2 == 0:
  print(s)
else:
  print(s-mm*2)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
cnt = 0
sum_ = 0
min_ = float('Inf')
for i in range(N):
    if a[i] < 0:
        cnt += 1
    min_ = min(min_, abs(a[i]))
    sum_ += abs(a[i])
if cnt % 2 == 0:
    print(sum_)
else:
    print(sum_ - 2 * min_)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))

#jは0なら反転なし、1なら反転
dp=[[0,0] for _ in range(N)] 
dp[0][0]=A[0]+A[1]
dp[0][1]=-1*(A[0]+A[1])
for i in range(1,N-1):
  dp[i][0] = max( dp[i-1][0]+A[i+1],        dp[i-1][1]+A[i+1] )
  dp[i][1] = max( dp[i-1][0]-2*A[i]-A[i+1], dp[i-1][1]+2*A[i]-A[i+1])
  
#print(dp)
print(max(dp[-2]))

Submission status: Accepted

Solution code:
# solution

data = int(input())
list = list(map(int,input().split()))
list.sort()

cnt_min = len([i for i in list if i < 0])
num_min = min([abs(i) for i in list])
sum_abs = sum([abs(i) for i in list])

if cnt_min%2 == 0:
    print(sum_abs)
else:
    print(sum_abs-2*num_min)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B,C=[],[]
for i in range(N):
  if A[i]>=0:
    B.append(A[i])
  else:
    C.append(-A[i])
if len(C)%2==0:
  ans=sum(B)+sum(C)
else:
  ans=sum(B)+sum(C)
  B.sort()
  C.sort()
  if len(B)==0:
    b=10**12
  else:
    b=B[0]
  a=min(b,C[0])
  ans-=2*a
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))

mini=float("inf")
summ=0
minus=0

for i in range(N):
  if A[i]<0:
    minus += 1
  mini = min(mini,abs(A[i]))
  summ += abs(A[i])

if minus%2==0:
  print(summ)
else:
  print(summ-2*mini)

Submission status: Accepted

Solution code:
n = int(input())
ns = list(map(int, input().split()))
abs_ns = [abs(i) for i in ns]
total = sum(abs_ns)
if sum(1 for i in ns if i < 0) % 2 == 0:
    print(total)
else:
    print(total - 2 * min(abs_ns))

Submission status: Accepted

Solution code:
import math  # noqa
import bisect  # noqa
import queue  # noqa


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    cnt_neg = 0
    abs_min = 1000000005
    for a in A:
        abs_min = min(abs_min, abs(a))
        if a < 0:
            cnt_neg += 1

    ans = 0
    for a in A:
        ans += abs(a)

    if cnt_neg % 2 != 0:
        ans -= 2 * abs_min

    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
fu=0
for i in range(n):
    if a[i]<0:
        fu+=1
        a[i]*=-1
if fu%2==0:
    print(sum(a))
else:
    print(sum(a)-2*min(a))

Submission status: Accepted

Solution code:
# knk_kei  0 in a の条件は不要 
n = int(input())
a = [int(i) for i in input().split()]
if len([i for i in a if i < 0]) % 2 == 0:
    print(sum([abs(i) for i in a]))
else:
    print(sum([abs(i) for i in a]) - 2*min([abs(i) for i in a]))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
sum_abs, min_abs, cnt_minus = 0, 10**9, 0
for ai in a:
    if ai < 0:
        cnt_minus += 1
    abs_ai = abs(ai)
    sum_abs += abs_ai
    if abs_ai < min_abs:
        min_abs = abs_ai
if cnt_minus % 2 == 0 or 0 in a:
    print(sum_abs)
else:
    print(sum_abs - 2*min_abs)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
# 欲しいのは絶対値の和、abs の絶対値、負の数
if len([i for i in a if i < 0]) % 2:
    print(sum([abs(i) for i in a]) - 2 * min([abs(i) for i in a]))
else:
    print(sum([abs(i) for i in a]))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
neg=0
for i in range(N):
    if A[i]<0:
        neg+=1
        A[i]*=-1

if neg%2==0:
    print(sum(A))
else:
    print(sum(A)-2*min(A))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
INF = 114514191981036436433-4
mi = 0
for i in range(n):
    if a[i] < 0:
        mi += 1
        a[i] *= (-1)
a.sort()

if mi%2 == 0:
    print(sum(a))
else:
    print(sum(a) - 2 * a[0])

Submission status: Accepted

Solution code:
A = int(input())
N = input()
counter = N.count("-")
N = list(map(int,N.split()))
N = list(map(abs,N))
N.sort()
if N[0] == 0:
    print(sum(N))
else:
    if counter % 2 == 0:
        print(sum(N))
    else:
        print(sum(N) - N[0] * 2)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())), dtype='int64')
am = a[np.where(a<=0)]

a2 = np.array(list(map(abs, a)), dtype='int64')
ans = sum(a2)
if len(am) % 2 == 1:
    m = np.amin(a2)
    ans -= 2 * m

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = 0
mi = 10**9 + 7
for i in range(n):
    if a[i] < 0:
        cnt += 1
        a[i] *= -1
    mi = min(mi, a[i])
print(sum(a)) if cnt % 2 == 0 else print(sum(a) - mi * 2)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
minus = 0
ans = 0
abs_min = float('inf')
for a in A:
  if a < 0:
    minus += 1
  ans += abs(a)
  abs_min = min(abs_min, abs(a))
if minus%2:
  ans -= abs_min*2

print(ans)

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()
A = iln()

# dp[N][2]とする。
# dp[x]はA[x]までの合計の最大値
# dp(x,0)はA[x]で反転しなかった場合、dp(x,1)はA[x]反転した結果を格納
dp = [[0 for _ in range(2)] for _ in range(N+1)]
# dp[0][1]は無効とする(反転結果が格納されるのはdp[1][1]から)。
dp[0][1] = -1*INF
for i in range(N):
    # A[i]を反転しなかった場合の最大値をdp[i+1][0]に格納
    dp[i+1][0] = max(dp[i][0]+A[i], dp[i][1]-A[i])
    # A[i]を反転した場合の最大値をdp[i+1][1]に格納
    dp[i+1][1] = max(dp[i][0]-A[i], dp[i][1]+A[i])

# 最後の数字は反転できないため、dp[N][0]を出力する
print(dp[N][0])

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()
A = iln()

dp = [[0 for _ in range(2)] for _ in range(N+1)]
dp[0][1] = -1*INF

for i in range(N):
    dp[i+1][0] = max(dp[i][0]+A[i], dp[i][1]-A[i])
    dp[i+1][1] = max(dp[i][0]-A[i], dp[i][1]+A[i])

# 最後の数字は操作できないため、dp[N][0]を出力する
print(dp[N][0])

Submission status: Accepted

Solution code:
import heapq
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int,input().split()))
cal = []
heapq.heapify(cal)
minus = 0
zero = False
for i in a:
    if i == 0:
        zero = True
    if i < 0:
        minus += 1
    heapq.heappush(cal,abs(i))

if minus % 2 == 0 or zero:
    print(sum(cal))
else:
    adjust = heapq.heappop(cal)
    print(sum(cal)-adjust)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
if a[0]<0: count=1
else: count = 0
ans, mina = abs(a[0]), abs(a[0])
flag = False
for i in range(1, n):
    ans += abs(a[i])
    mina = min(mina, abs(a[i]))
    if a[i]<0: count += 1
if count%2 or a.count(0): print(ans-mina*2)
else: print(ans)

Submission status: Accepted

Solution code:
整数 = int
入力 = input
各々 = map
文字列 = str
分割 = 文字列.split
配列 = list
総和 = sum
絶対値 = abs
出現回数 = 配列.count
出力 = print
零 = 0
真偽 = bool
又 = 真偽.__or__
且 = 真偽.__and__
余 = 整数.__mod__
和 = 整数.__add__
積 = 整数.__mul__
弐 = 2
壱 = 1
最小値 = min
差 = 整数.__sub__
負 = lambda 整数: 整数 < 零


長さ = 整数(入力())
整数列 = 配列(各々(整数, 分割(入力())))
絶対値列 = 配列(各々(絶対値, 整数列))
絶対値の和 = 総和(絶対値列)
零の数 = 出現回数(整数列, 零)
負の数の数 = 総和(各々(負, 整数列))
出力(差(絶対値の和,
      積(最小値(絶対値列),
          積(弐,
              差(壱,
                 整数(又(真偽(零の数),
                         真偽(余(和(負の数の数, 壱), 弐)))))))))

Submission status: Accepted

Solution code:
整数 = int
入力 = input
各々 = map
文字列 = str
分割 = 文字列.split
配列 = list
総和 = sum
絶対値 = abs
出現回数 = 配列.count
出力 = print
零 = 0
真偽 = bool
又 = 真偽.__or__
且 = 真偽.__and__
余 = 整数.__mod__
和 = 整数.__add__
積 = 整数.__mul__
弐 = 2
壱 = 1
最小値 = min
差 = 整数.__sub__
負 = lambda 整数: 整数 < 零


長さ = 整数(入力())
整数列 = 配列(各々(整数, 分割(入力())))
絶対値列 = 配列(各々(絶対値, 整数列))


絶対値の和 = 総和(絶対値列)
零の数 = 出現回数(整数列, 零)
負の数の数 = 総和(各々(負, 整数列))


出力(差(絶対値の和,
      積(最小値(絶対値列),
          積(弐,
              差(壱,
                 整数(又(真偽(零の数),
                         真偽(余(和(負の数の数, 壱), 弐)))))))))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
min_abs=float("inf")
ans=0;cnt=0
for i in range(N):
    if A[i]<0:
        cnt+=1
    min_abs=min(min_abs,abs(A[i]))
    ans+=abs(A[i])
if cnt%2==0:
    print(ans)
else:
    print(ans-2*min_abs)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
n = sum([1 for i in range(N) if A[i] < 0])
abs_A = [abs(a) for a in A]
ans = sum(abs_A)
if n % 2 == 0:
  print(ans)
else:
  print(ans-2*min(abs_A))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
ABS=sorted(list(map(abs,A)))
x=1
for a in A:
  if a==0:
    print(sum(ABS))
    exit(0)
  if a<0:
    x*=-1
if x==1:
  print(sum(ABS))
else:
  print(sum(ABS)-2*ABS[0])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr())
Aabs = np.abs(A)
negative = np.count_nonzero(A < 0)
answer = Aabs.sum()
if negative&1:
    answer -= 2 * np.min(Aabs)

print(answer)
#

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr())
if np.count_nonzero(A) != len(A):
    answer = np.abs(A).sum()
else:
    negative = np.count_nonzero(A < 0)
    if negative%2 == 0:
        answer = np.abs(A).sum()
    else:
        answer = np.abs(A).sum()
        answer -= 2 * np.min(np.abs(A))

print(answer)
# 37

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = 0
tmp = 1000000005
for i in range(n):
  if a[i] < 0:
    a[i] = -a[i]
    cnt += 1
  tmp = min(tmp, a[i])
if cnt % 2 == 0:
  print(sum(a))
else:
  print(sum(a) - 2 * tmp)

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
A = nl()

abstotal = sum([abs(i) for i in A])
absmin = min([abs(i) for i in A])
if len([i for i in A if i < 0]) % 2 == 0:
    ans = abstotal
else:
    ans = abstotal - 2 * absmin
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
assert len(A) == N

def solve():
    negcnt = len([a for a in A if a<0])
    aa = [abs(a) for a in A]
    if negcnt % 2 == 0:
        return sum(aa)
    mv = min(aa)
    return sum(aa) -2*mv
print(solve())

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
n = len(list(filter(lambda x: x<0, A)))
A.sort(key=abs)
if n&1 == 0:
    print(sum(map(abs, A)))
else:
    print(sum(map(abs, A[1:]))-abs(A[0]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
n = len(list(filter(lambda x: x<0, A)))
A.sort(reverse=True, key=lambda x: abs(x))
if n&1 == 0:
    print(sum(map(abs, A)))
else:
    print(sum(map(abs, A[:(N-1)]))-abs(A[-1]))

Submission status: Accepted

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))

def main():
    n = II()
    aa = MII()
    dp = [[0]*(2) for _ in range(n)]
    dp[0][0] = aa[0]
    dp[0][1] = -aa[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0]+aa[i], dp[i-1][1]-aa[i])
        dp[i][1] = max(dp[i-1][0]-aa[i], dp[i-1][1]+aa[i])
    print(max(dp[n-2][0]+aa[-1], dp[n-2][1]-aa[-1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(lambda x: int(x),input().split()))
flag = 0
cnt = 0
for i in A:
    if i < 0:
        cnt += 1
    elif i == 0:
        flag = 1
cnt %= 2
A = list(map(lambda x: abs(x), A))
if flag or cnt == 0:
    print(sum(A))
else:
    print(sum(A)-2*min(A))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
A = list(map(int,input().split()))
if 0 in A:
    s = 0
    for i in A:
        s += abs(i)
    print(s)
c = 0
for i in range(N):
    if A[i] < 0:
        c += 1
        A[i] *= -1
Min = min(A)
s = 0
for i in A:
    s += i
if c % 2 == 1:
    s -= Min * 2
if 0 not in A:
    print(s)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int,input().split()))
count = 0
ans = 0
dum2 = 0
dum = abs(s[0])
for i in range(n):
  if s[i] < 0:
    count += 1
    dum2 = -s[i]
  else:
    dum2 = s[i]
  dum = min(dum,dum2)
  ans += dum2
if count%2 == 0:
  print(ans)
else:
  print(ans-dum*2)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
hu=0
min_=10**9+1
total=0
for i in range(n):
    if a[i]<0:
        hu+=1
    if abs(a[i])<min_:
        min_=abs(a[i])
    total+=abs(a[i])
print(total if hu%2==0 else total-min_*2)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

minus = 0
for i in range(N):
    if A[i] < 0:
        minus += 1

absed = sorted([abs(a) for a in A])
if minus % 2 == 0:
    print(sum(absed))
else:
    print(sum(absed) - absed[0]*2)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mi = 0
p = []
for i in range(n):
    if a[i] < 0:
        mi += 1
        a[i] = -a[i]
if mi % 2 == 0:
    print(sum(a))
elif mi % 2 == 1:
    print(sum(a)-2*min(a))

Submission status: Accepted

Solution code:
n=int(input())

t = list(map(int,input().split()))

count = 0

for i in t:
    if i < 0:
        count += 1

memo = []

for i in t:
    memo.append(abs(i))
memo.sort()

if count%2==0:
    print(sum(memo))
else:
    print(sum(memo)-memo[0]*2)

Submission status: Accepted

Solution code:
# DP

n = int(input())
A = list(map(int, input().split()))
dp = [[None] * 2 for _ in range(n + 1)]
dp[0][0] = 0
dp[0][1] = -float("inf")

for i in range(1, n + 1):
    dp[i][0] = max(dp[i - 1][0] + A[i - 1], dp[i - 1][1] - A[i - 1])
    dp[i][1] = max(dp[i - 1][0] - A[i - 1], dp[i - 1][1] + A[i - 1] )

print(dp[n][0])

Submission status: Accepted

Solution code:
# x < y  を反転できる
#
# かっこいい手法

n = int(input())
A = list(map(int, input().split()))
absA = list(map(abs, A))
num_le0 = 0
for a in A:
    if a <= 0:
        num_le0 += 1
S = sum(absA)
ans = None

if num_le0 == 0 or num_le0 % 2 == 0:
    ans = S
else:
    ans = S - 2 * min(absA)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = map(int, input().split())

zero = False
minus = 0
mn = 99999999999999999
sum = 0
for i in a:
    if i == 0:
        zero = True
    if i < 0:
        minus += 1
    sum += abs(i)
    mn = min(mn, abs(i))

if not zero and minus % 2 != 0:
    sum -= mn * 2

print(sum)

Submission status: Accepted

Solution code:
input()
ms = list(map(int,input().split()))
ms_abs = [abs(m) for m in ms]
ms_minus = [m for m in ms if m < 0]
if len(ms_minus) % 2 == 0:
    print(sum(ms_abs))
else:
    print(sum(ms_abs) - 2*min(ms_abs))

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
A = list(map(int,input().split()))

"""
方針
符号を変えられるのは偶数箇所
ソートしてどこまでが負の値かを調べる
境界のところで符号を変えるかは境界付近の値を見て決める
"""

A.sort()

ans,pt = 0,bisect_left(A,0)

if pt % 2 == 0:
    ans = sum(map(abs,A))
else:
    if pt == N:
        ans = sum(map(abs,A)) + 2*A[N-1]
    else:
        if A[pt-1] + A[pt] >= 0:
            ans = sum(map(abs,A)) + 2*A[pt-1]
        else:
            ans = sum(map(abs,A)) - 2*A[pt]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
An = list(map(int,input().split()))
num = 0
for A in An:
  if A < 0: num+=1
An = list(map(lambda x: abs(x), An))
if num%2==0:
  print(sum(An))
else:
  print(sum(An) - 2*min(An))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
nega = [a for a in A if a < 0]
A_abs = sorted(abs(a) for a in A)
if len(nega) % 2 == 0:
  ans = sum(A_abs)
else:
  ans = sum(A_abs) - 2 * A_abs[0]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = 10**9+1
ans = 0
cnt = 0
flag = 0
for i in range(n):
  if a[i] < 0:
    cnt += 1
  elif a[i] == 0:
    flag = 1
  ans += abs(a[i])
  m = min(m,abs(a[i]))
if cnt % 2 == 0 or flag:
  print(ans)
else:
  print(ans-2*m)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

ans = 0
cnt = 0
m = 10 ** 9
for a in A:
    if a < 0:
        cnt += 1
    ans += abs(a)
    if m > abs(a):
        m = abs(a)

if cnt % 2 == 1:
    print(ans - 2 * m)
else:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
cnt = 0
mini = float("inf")
for i in range(N):
    ans += abs(A[i])
    mini = min(mini, abs(A[i]))
    if A[i] < 0:
        cnt += 1
        
if cnt % 2:
    ans -= 2 * mini
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
aa = list(map(int, input().split()))

mina = abs(aa[0])
nm = 0
for i in range(n):
    mina = min(mina, abs(aa[i]))
    if aa[i] < 0:
        nm += 1

if nm % 2 == 1 and mina > 0:
    print(sum(map(abs, aa)) - 2 * mina)
else:
    print(sum(map(abs, aa)))

Submission status: Accepted

Solution code:
N = int(input())
numbers = [int(x) for x in input().split()]

negative_sign_count = len([x for x in numbers if x < 0])
abs_numbers = [abs(x) for x in numbers]
abs_numbers.sort()

# 負の数が偶数 or 0を含む場合はすべての符号を正に反転できる
if negative_sign_count % 2 == 0 or 0 in numbers:
  print(sum(abs_numbers))
# それ以外はひとつだけ正にできない数があるので、絶対値が一番小さい数を負にする
else:
  print(sum(abs_numbers[1:]) - abs_numbers[0])