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:
N=int(input())
import numpy as np
A=np.array(list(map(int,input().split())))
m=np.sum(A<0)
flag=np.any(A==0)
A=np.abs(A)
ans=np.sum(A)
if (m%2==1)and(not flag):
  x=np.min(A)
  ans-=x*2

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
import numpy as np
A=np.array(list(map(int,input().split())))
m=np.sum(A<0)
A=np.abs(A)
ans=np.sum(A)
if m%2==1:
  x=np.min(A)
  ans-=x*2

print(ans)

Submission status: Accepted

Solution code:

N = int(input())
A = [int(i)for i in input().split()]
p = 0
min = 10**9 + 1
ans = 0
for i in A:
    if i < 0:
        p += 1
    i = abs(i)
    ans += i
    if min > i:
        min = i
if p%2 ==1:
    ans -= min*2
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[28]:


import numpy as np


# In[29]:


N = int(input())
A = np.array([int(x) for x in input().split()])


# In[33]:


A = A.astype('int64')


# In[34]:


if np.count_nonzero(A < 0) % 2 == 0:
    print(sum(abs(A)))
else:
    print(sum(abs(A)) - 2 * min(abs(A)))


# In[ ]:





# In[ ]:

Submission status: Accepted

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

    dp = [[-1] * 2 for _ in range(n + 1)]
    dp[0][False] = 0
    # dp[idx][マイナスをかける必要があるか]:=総和の最大値

    for j, x in enumerate(a):
        if dp[j][True] == -1:
            dp[j + 1][False] = dp[j][False] + x
            dp[j + 1][True] = dp[j][False] - x
        else:
            dp[j + 1][False] = max(dp[j][False] + x, dp[j][True] - x)
            dp[j + 1][True] = max(dp[j][False] - x, dp[j][True] + x)
    return dp[n][False]


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
a = tuple(sorted(map(int, input().split())))
b = tuple(sorted(map(abs, a)))

j = bisect_left(a, 0)
m = a[:j]

if len(m) % 2 == 0:
    print(sum(b))
else:
    print(sum(b) - min(b) * 2)

Submission status: Accepted

Solution code:
INF = 1e10

n = int(input())
a = list(map(int, input().split()))
flag = True
a_min = INF
ans = abs(a[-1])
for i in range(n-1):
    ans += abs(a[i])
    if a[i]<0:
        a[i] = -1*a[i]
        a[i+1] = -1*a[i+1]
    a_min = min(a_min, abs(a[i]))
a_min = min(a_min, abs(a[-1]))
if a[-1]<0:
    ans = ans - 2*a_min
print(ans)

Submission status: Accepted

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

dp = [[0,-10**9] for _ in range(n+1)]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input().strip())
A = list(map(int, input().strip().split(" ")))
minus_count = 0
minimum = float("inf")
S = 0
for a in A:
    if a < 0:
        minus_count += 1
        a *= -1
    minimum = min(a, minimum)
    S += a
if minus_count % 2 == 1:
    S -= 2*minimum

print(S)

Submission status: Accepted

Solution code:
n=input()
a=list(map(int,input().split()))
n=sum(x<0 for x in a)
a=list(map(abs,a))
s=sum(a) if n%2==0 else sum(a)-min(a)*2
print(s)

Submission status: Accepted

Solution code:
n=input()
a=list(map(int,input().split()))
n=sum(x<0 for x in a)
a=list(map(lambda x: abs(x),a))
s=sum(a) if n%2==0 else sum(a)-min(a)*2
print(s)

Submission status: Accepted

Solution code:
n=input()
a=list(map(int,input().split()))
n=sum(x<0 for x in a)
a=list(map(lambda x: abs(x),a))
m=min(a)
s=sum(a) if n%2==0 else sum(a)-m *2
print(s)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
neg_sum=sum(x<0 for x in a)
a=list(map(lambda x: abs(x),a))
m=min(a)
s=sum(a)
if neg_sum%2 : s-=m*2
print(s)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    cnt_minus = 0
    zero_idx = []
    for i, a in enumerate(A):
        if a < 0:
            cnt_minus += 1
        elif a == 0:
            zero_idx.append(i)
    flag = False
    for z in zero_idx:
        if (0 < z and A[z-1] < 0) or (z < N - 1 and A[z+1] < 0):
            flag = True

    ans = 0
    if cnt_minus % 2 == 0:
        ans = sum(abs(a) for a in A)
    elif flag:
        ans = sum(abs(a) for a in A)
    else:
        ans = sum(abs(a) for a in A) - min(abs(a) for a in A) * 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

p=0
for i in range(n):
    if l[i]<0:
        l[i]=-l[i]
        p+=1
if p/2==p//2:
    print(sum(l))
else:
    print(sum(l)-2*min(l))

Submission status: Accepted

Solution code:
#(ai,ai+1),(ai+1,ai+2)...(aj-1,aj)に-1を掛けると
#ai,ajに-1を掛けることができる

n = int(input())
a = list(map(int, input().split()))
n=len(a)
mns = [ai for ai in a if ai<0]
pls = [ai for ai in a if ai>=0]

mns.sort()
pls.sort()
#print(mns)
#print(pls)
lm = len(mns)
m_rem = 0
if lm%2:
    if pls:
        if pls[0]<-1*mns[-1]:
            tmp = -1*mns[-1]
            mns[-1] = -1*pls[0]
            pls[0] = tmp
    m_rem = mns.pop()

print(sum(pls)-sum(mns) + m_rem)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
minabs=10**9+1
minus=0
allsum=0
for i in a:
  if i<0:
    minus+=1
  minabs=min(minabs,abs(i))
  allsum+=abs(i)

if minus%2==1:
  allsum-=minabs*2
print(allsum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = input()
A = list(map(int, input().split()))
plus = []
minus = []
for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(-a)
if len(minus) % 2 == 0:
    sum_value = sum(plus + minus)
    print(sum_value)
else:
    min_value = min(plus + minus)
    sum_value = sum(plus + minus) - min_value*2
    print(sum_value)

Submission status: Accepted

Solution code:
def p_d():
    n = int(input())
    *a, = map(int, input().split())
    *b, = filter(lambda x: x <= 0, a)
    *c, = map(abs, a)
    if len(b) & 1 == 0:
        print(sum(c))
    else:
        print(sum(c) - 2 * sorted(c)[0])


if __name__ == '__main__':
    p_d()

Submission status: Accepted

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

if cnt % 2 == 0:
	print(ans)
else:
	print(ans - 2*abs_min)

Submission status: Accepted

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

Submission status: Accepted

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

    # 要素の絶対値
B = list(map(abs, A))

    # 負の要素の個数
C = [a for a in A if a < 0]
if len(C) % 2 == 0:
  print(sum(B))
else:
        # 最小値を負として計算する
  print(sum(B) - min(B)*2)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
m = float('inf')
i = 0
total = 0
minus = 0
while i < n:
    if a[i] < 0:
        m = min(m, -a[i])
        total -= a[i]
        minus += 1
    else:
        m = min(m, a[i])
        total += a[i]
    i += 1
if minus % 2 == 1:
    ans = total - 2 * m
else:
    ans = total
print(ans)

Submission status: Accepted

Solution code:
import heapq


n = int(input())
a = [int(_) for _ in input().split()]
q = []
heapq.heapify(q)
i = 0
total = 0
minus = 0
while i < n:
    if a[i] < 0:
        heapq.heappush(q, -a[i])
        total -= a[i]
        minus += 1
    else:
        heapq.heappush(q, a[i])
        total += a[i]
    i += 1
if minus % 2 == 1:
    ans = total - 2 * heapq.heappop(q)
else:
    ans = total
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
count_f=0
count_0=0
B=[]
for i in range(N):
  B += [abs(A[i])]
  if A[i]==0:
    count_0 +=1
  elif A[i]<0:
    count_f +=1
if count_f%2==0 or count_0>0:
  print(sum(B))
else:
  print(sum(B)-2*min(B))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
abA = [abs(i) for i in A]
mc = [i < 0 for i in A].count(True)
mv = min(abA)
sm = sum(abA)

if mc % 2 == 0:
    print(sm)
else:
    print(sm - 2 * mv)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split(' ')))

if len([a for a in A if a == 0]) > 0:
    n = sum(map(abs, A))
    print(n)

elif len([a for a in A if a < 0]) % 2 == 0:
    n = sum(map(abs, A))
    print(n)

else:
    A.sort(key=lambda x: abs(x))
    n = sum(map(abs, A[1:]))
    n -= abs(A[0])
    print(n)

Submission status: Accepted

Solution code:
import math

INF = float("inf")

# Check

def good(N, A):
    even = 0
    zero = 0
    c = 0

    ans = 0
    for i in A:
        if i < 0:
            c += 1
        elif i == 0:
            even = 0
            c = 0
        else:
            if c % 2 != 0:
                even += 1
            c = 0
        ans += abs(i)

    if c != 0 and c % 2 != 0:
        even += 1

    if even % 2 == 0:
        print(ans)
    else:
        print(ans - min([abs(i) for i in A if abs(i) > 0]) * 2)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[0 for i in range(2)] for i in range(N+1)]

    dp[0][0] = 0
    dp[0][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])

    print(dp[N][0])
    # good(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

# Check


def main():
    N = int(input())
    A = list(map(int, input().split()))
    even = 0
    zero = 0
    c = 0

    ans = 0
    for i in A:
        if i < 0:
            c += 1
        elif i == 0:
            even = 0
            c = 0
        else:
            if c % 2 != 0:
                even += 1
            c = 0
        ans += abs(i)

    if c != 0 and c % 2 != 0:
        even += 1

    if even % 2 == 0:
        print(ans)
    else:
        print(ans - min([abs(i) for i in A if abs(i) > 0]) * 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sum_list = [ ]
nagative_count = 0
for i in range(N):
    if An[i] < 0 :
        sum_list.append(An[i]*(-1))
        nagative_count += 1
    else: 
        sum_list.append(An[i])

if nagative_count%2 == 0:
    print(sum(sum_list))
else:
    sum_list.sort()
    sum_list[0] = sum_list[0]*(-1)
    print(sum(sum_list))

Submission status: Accepted

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

zero = 0
minus = 0
for i in range(n):
    if a[i] == 0:
        zero = 1
    elif a[i] < 0:
        minus += 1
    a[i] = abs(a[i])

a.sort()
if zero or minus%2 == 0:
    print(sum(a))
else:
    print(sum(a[1:])-a[0])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    minA=INF
    c_m=0
    sumA=0
    for i in A:
        if i<0:
            c_m+=1
        minA=min(minA,abs(i))
        sumA+=abs(i)
    if c_m%2==1:
        print(sumA-2*minA)
    else:
        print(sumA)
        
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
min_abs = 10**9
count_n = 0
flag_z = False

for i in a:
    if flag_z:
        if i >= 0:
            ans += i
        else:
            ans -= i

    else:
        if i == 0:
            flag_z = True
        elif i > 0:
            min_abs = min(min_abs, i)
            ans += i
        else:
            count_n += 1
            min_abs = min(min_abs, abs(i))
            ans -= i

if not (flag_z or count_n % 2 == 0):
    ans -= min_abs*2

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

al = list(map(int,input().split()))
absl = []
minus = 0
for a in al:
    absl.append(abs(a))
    if a < 0:
        minus += 1

if minus % 2 == 0:
    print(sum(absl))
else:
    print(sum(absl) - 2 * min(absl))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A_=sorted([i if i>0 else -i for i in A])
print(sum(A_)-A_[0]*2*((N-len([i for i in A if i>0]))%2))

Submission status: Accepted

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

Sum = 0
minus_Sum = 0
min = 10**9

for i in range(N):
    Sum += abs(A[i])
    if min > abs(A[i]):
        min = abs(A[i])
    
    if A[i] < 0:
        minus_Sum += 1
        
if minus_Sum % 2 == 0:
    print(Sum)
else:
    print(Sum - 2*min)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)

n = int(input())
a = list(map(int, input().split()))
dp = [[None]*(2) for _ in range(n+1)]

dp[n-1][0] = a[n-1]
dp[n-1][1] = -a[n-1]

for i in reversed(range(n-1)):
    for j in range(2):
        #print('\n# i: ' + str(i))
        # Unexe
        unexe_unexe = a[i] + dp[i+1][0]
        exe_unexe = -a[i] + dp[i+1][1]
        dp[i][0] = max(unexe_unexe, exe_unexe)

        # Exe
        unexe_exe = a[i] + dp[i+1][1]
        exe_exe = -a[i] + dp[i+1][0]
        dp[i][1] = max(unexe_exe, exe_exe)

#print(dp)
#print(max(dp[0][0], dp[0][1]))
print(dp[0][0])

Submission status: Accepted

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

negcnt = 0
mina = 10 ** 10
suma = 0
for i in a:
  if i < 0:
    negcnt += 1
  if mina > abs(i):
    mina = abs(i)
  suma += abs(i)

if negcnt % 2 == 1:
  ans = suma - 2*mina
else:
  ans = suma

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
dp=[[0]*2 for _ in range(N+1)]
dp[0][1]=-float("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])
print(dp[-1][0])

Submission status: Accepted

Solution code:
N = int(input())
A =sorted( list(map(int, input().split())))
A_abs = list(map(abs, A))
flag = 0
for i in range(N):
    if A[i]<0:
        flag += 1
    else:
        break
if flag%2==0:
    print(sum(A_abs))
else:
    A_abs_s = sorted(A_abs)
    A_abs_s[0] = -1*A_abs_s[0]
    print(sum(A_abs_s))

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
k=[]
t=0
ans=0
for i in range(n):
  ans+=abs(d[i])
  if d[i]<=0:
    t+=1
for i in range(len(d)):
  k.append(abs(d[i]))
k.sort()
if t%2:
  ans-=2*k[0]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    switch_count = N if N%2 == 0 else N-1
    A.sort()
    sumA = sum(A)
    answer = sumA
    prev = sumA
    for i in range(2,switch_count+1,2):
        a = prev - A[i-1]*2 - A[i-2]*2
        answer = max(a,answer)
        prev = a
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]

cnt = 0
m = 1e10
ans = 0
for a in A:
    if a < 0:
        cnt += 1
    ans += abs(a)
    m = min(abs(a), m)
if cnt % 2 == 0:
    print(ans)
else:
    print(ans - m*2)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()
plus_a = [abs(a) for a in A]
z_cnt = 0
minus_cnt = 0
for i in A:
    if i == 0:
        z_cnt += 1
    elif i < 0:
        minus_cnt += 1


if z_cnt or minus_cnt % 2 == 0:
    print(sum(plus_a))
else:
    print(sum(plus_a) - min(plus_a) * 2)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
if a.count(0) == 0:
    hu_count = 0
    min = 10 ** 9
    for i in range(0,n):
        if a[i] < 0:
            hu_count += 1
            a[i] = -1 * a[i]
        if min > a[i]:
            min = a[i]
    if hu_count % 2 == 0:
        print(sum(a))
    else:
        print(sum(a) - min - min)
else:
    for i in range(0,n):
        if a[i] < 0:
            a[i] = -1 * a[i]
    print(sum(a))

Submission status: Accepted

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

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

    a = list(map(abs, a))
    a.sort()
    if cnt % 2:
        ans = sum(a[1:]) - a[0]
    else:
        ans = sum(a)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=sum(map(abs,a))
c=min(list(map(abs,a)))
z=[]
for i in a:
    if i<0:
        z.append(i)
x=len(z)%2
if x:
    print(s-2*c)
else:
    print(s)

Submission status: Accepted

Solution code:
input()
a = list(map(int, input().split()))
s = sum(map(abs, a))
n = sum(x < 0 for x in a)
if n % 2:
    s -= 2 * min(map(abs, a))
print(s)

Submission status: Accepted

Solution code:
def main():
    # x,y = map(int,input().split())           x=1,y=2
    # a = input().split()                      a=['1','2','3',...,'n']
    # a = list(map(int,input().split()))       a=[1,2,3,4,5,...,n]
    # li = input().split('T')	              FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    # 複数行の「1 2 3 4」型の入力を一配列に
    # x = sorted([list(map(int, input().split())) for _ in range(n)])
    # ソート x.sort(key=lambda y:y[1])
    # [chr(i) for i in range(97, 97+26)] 英語小文字リスト
    # [chr(i) for i in range(65, 65+26)] 英語大文字リスト atcoder
    # ord(c) chr(2) alphabet <=> number
    n=int(input())
    a = list(map(int,input().split()))
    cnt=0
    for i in range(n):
        if a[i]<0:
            a[i]*=-1
            cnt+=1
    a.sort()
    S=sum(a)

    print(S) if cnt%2==0 else print(S-2*a[0])
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7


n = INT()
a = MAP()

flag = False
cnt=0
for i in a:
    if i==0:
        flag = True
        break
    if i<0:
        cnt+=1
if cnt%2==0:
    flag = True

if flag:
    l = [abs(i) for i in a]
    print(sum(l))
else:
    l = [abs(i) for i in a]
    print(sum(l)-(2*min(l)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
list1 = list(map(int,input().split()))
"""
for i in range(2):
	for i in range(n-1):
		if list1[i] < 0 and list1[i+1] < 0:
			list1[i] = abs(list1[i])
			list1[i+1] = abs(list1[i+1])
		elif (list1[i] < 0 and (abs(list1[i]) > abs(list1[i+1]))) or \
		(list1[i+1] < 0 and (abs(list1[i+1]) > abs(list1[i]))):
			list1[i] = list1[i]*-1
			list1[i+1] = list1[i+1]*-1


"""
count = 0
for i in range(n):
	if list1[i] < 0:
		count += 1
		list1[i] = abs(list1[i])
if count%2 == 0:
	print(sum(list1))
else:
	list1.sort()
	print(sum(list1)-list1[0]*2)

Submission status: Accepted

Solution code:
# D - Flipping Signs

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

n_minus = len([x for x in A if x < 0])

if n_minus % 2 == 0:
    print(sum([abs(x) for x in A]))
else:
    print(sum([abs(x) for x in A]) - 2*abs(min(A, key=abs)))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
A=tuple(map(int,input().split()))
B=[abs(i) for i in A]
o=0
for i in A:
    if i<0:
        o+=1
if o%2==0:
    print(sum(B))
else:
    print(sum(B)-min(B)*2)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N = I()
A = LI()
k = int(1)
for i in A:
    if i<0:
        k *=(-1)
    elif i==0:
        k = 0

for i in range(N):
    A[i] = abs(A[i])
sumA = sum(A)
if k<0:
    ans = sumA-min(A)*2
else:
    ans = sumA

print(ans)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

N = int(input())
A = [0] + list(map(int, input().split()))

dp = makelist(N+1, 2)
dp[1][0] = A[1]
dp[1][1] = -int(1e9)
for i in range(2, N+1):
    dp[i][0] = A[i] + max(dp[i-1][0], dp[i-1][1])
    dp[i][1] = -A[i] + max(dp[i-1][0] + (-A[i-1])*2, dp[i-1][1] + A[i-1]*2)

ans = max(dp[N][0], dp[N][1])
print(ans)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

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

A.sort()
for i in range(N-1):
    if i % 2 == 0:
        if A[i] + A[i+1] < 0:
            A[i] = -A[i]
            A[i+1] = -A[i+1]
            
print(sum(A))

Submission status: Accepted

Solution code:
import sys
import bisect
import collections
import fractions
import heapq


def slove():
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    cnt = 0
    t = 0
    for i in range(n):
        if a[i] < 0:
            cnt += 1
        a[i] = abs(a[i])
        t += a[i]
    a.sort()
    if cnt % 2 == 0:
        print(t)
    else:
        print(t - abs(a[0]) * 2)


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

negA = []
posA = []
for a in A:
    if a >= 0:
        posA.append(a)
    else:
        negA.append(a)

ans = sum(posA) - sum(negA)

if len(negA) % 2 == 1:
    ans -= min([abs(a) for a in A]) * 2

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
cnt = 0
abs_sum = 0
for i in A:
    abs_sum += abs(i)
    if i < 0:
        cnt += 1
mi = min([abs(i) for i in A])
if cnt % 2 == 0:
    print(abs_sum)
else:
    print(abs_sum-(mi*2))

Submission status: Accepted

Solution code:
import heapq
n = int(input())
a = list(map(int,input().split()))
count = 0
for i in a:
    if i < 0:
        count += 1
abs_a = list(map(abs,a))
if 0 in a or count % 2 == 0:
    print(sum(abs_a))
else:
    heapq.heapify(abs_a)
    min_a = heapq.heappop(abs_a)
    print(sum(abs_a)-min_a)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
cnt = 0
zcnt = a.count(0)
for i in range(N):
    if a[i] < 0:
        cnt += 1

total = 0
if cnt % 2 == 0 or (cnt % 2 != 0 and zcnt > 0):
    for i in range(N):
        total += abs(a[i])
else:
    tmp = 10 ** 9
    for i in range(N):
        total += abs(a[i])
        tmp = min(tmp, abs(a[i]))
    total -= 2 * tmp

print(total)

Submission status: Accepted

Solution code:
a=int(input())
lis=list(map(int,input().split()))
lis=sorted(lis)
i=0
while i<=a-2 and lis[i]<0:
  if lis[i]<=0 and lis[i+1]>=0:
    if -1*lis[i]>lis[i+1]:
      lis[i],lis[i+1]=-lis[i],-lis[i+1]
  elif lis[i]<=0 and lis[i+1]<=0:
    lis[i],lis[i+1]=-lis[i],-lis[i+1]
  i+=2
print(sum(lis))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
cnt = sum(a < 0 for a in A)
sumabs = sum(abs(a) for a in A)
if cnt % 2 == 0:
    print(sumabs)
else:
    print(sumabs - 2 * min(abs(a) for a in A))

Submission status: Accepted

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

dp = [[0 for i in range(2)] for i in range(N+1)]

dp[0][0] = 0
dp[0][1] = -10000000

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])
print(dp[N][0])

Submission status: Accepted

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

cnt = 0

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

A = [abs(i) for i in A]
if cnt % 2 == 0:
    print(sum(A))
else:
    print(sum(A) - 2 * min(A))

Submission status: Accepted

Solution code:
import numpy as np

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

A2 = np.abs(A)
x = A2.min()
s = A2.sum()
A3 = A < 0
if A3.sum() % 2 == 0:
    print(s)
else:
    print(s-2*x)

Submission status: Accepted

Solution code:
import numpy as np

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

A2 = np.abs(A)
x = A2.min()
s = A2.sum()
A3 = A < 0
if sum(A3) % 2 == 0:
    print(s)
else:
    print(s-2*x)

Submission status: Accepted

Solution code:
import numpy as np

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

A2 = abs(A)
x = min(A2)
A3 = A < 0
if sum(A3) % 2 == 0:
    print(sum(A2))
else:
    print(sum(A2)-2*x)

Submission status: Accepted

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

cnt=0
S=0
mi=10000000000
C0=False

for i in range(N):
    mi=min(mi,abs(A[i]))
    if A[i]>0:
        S+=A[i]
    elif A[i]==0:
        C0==True
    elif A[i]<0:
        cnt+=1
        S+=(-A[i])

if cnt%2==0 or C0==True:
    print(S)
else:
    print(S-mi*2)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [[0 for i in range(2)] for i in range(N+1)]
dp[0][1] = -10**9

#print(dp)

for i in range(N):
    #print(A[i])
    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])

#print(dp)
print(dp[N][0])

Submission status: Accepted

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

K = len([a for a in A if a < 0])
B = sorted([abs(a) for a in A])

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

Submission status: Accepted

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

cnt = 0
for i in range(N):
    if A[i] < 0:
        cnt += 1
        A[i] = -1 * A[i]
if cnt % 2 == 0:
    print(sum(A))
else:
    A.sort()
    print(sum(A) - A[0] * 2)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [0]*N
numofminus = 0
minabs = 10**9  # 最も絶対値が小さいもの
for i in range(N):
    B[i] = abs(A[i])
    if A[i] < 0:
        numofminus += 1
    if abs(A[i]) < minabs:
        minabs = abs(A[i])

if numofminus % 2 == 1:
    ans = sum(B) - 2 * minabs
else:
    ans = sum(B)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
count = 0
ans = 0
num = float("inf")

for i in range(n):
	a = A[i]
	if a < 0:
		count += 1
	ans += abs(a)
	num = min(num, abs(a))

if count % 2:
	print(ans - 2*(num))
else:
	print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
n=sum(list(map(lambda x: x<0,a)))
c0=sum(list(map(lambda x: x==0,a)))
if c0:
    print(sum(list(map(abs,a))))
    exit(0)
if n&1:
    print(sum(list(map(abs,a)))-2*min(list(map(abs,a))))
else:
    print(sum(list(map(abs,a))))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())

A=[int(i) for i in input().split()]

flg=1
for num in A:
    if num < 0:
        flg*=(-1)
        
B=[abs(i) for i in A]

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
minus = sum([1 if x<0 else 0 for x in A])
if minus%2==1:
    absA = list(map(abs, A))
    mn = min(absA)
    print(sum(absA)-2*mn)
else:
    print(sum(map(abs, A)))