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:
# ABC125D - Flipping Signs
def main():
    # neg % 2 == 0 -> all negatives disappear
    # else -> move all neg to the smallest one (abs(i))
    # if 0 in A -> move all neg there but min will be 0
    N, *A = map(int, open(0).read().split())
    mi = abs(min(A, key=abs))
    abs_sum = sum(abs(i) for i in A)
    neg = sum(i < 0 for i in A)
    ans = abs_sum if neg % 2 == 0 else abs_sum - mi * 2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = 0
c = 0
m = 10 ** 10

for x in a:
    if x < 0:
        c += 1
    
    s += abs(x)
    m = min(m, abs(x))
    
if c % 2 != 0:
    s -= 2 * m
    
print(s)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
m = sum(1 for i in a if i < 0)
z = any(i==0 for i in a)
if m%2 == 0 or z:
    print(sum(abs(i) for i in a))
else:
    # print(sum(abs(i) for i in a),min(abs(i) for i in a))
    print(sum(abs(i) for i in a)-2*abs(min(abs(i) for i in a)))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=[abs(i) for i in A]
P=0
for i in A:
    if i<0:P +=1
    elif i==0:print(sum(B));exit()

print(sum(B) if P%2==0 else sum(B)-2*min(B))

Submission status: Accepted

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

flag=True # Ai<0なるiの個数が偶数か
for i in range(N):
    if A[i]<0:
        flag=not flag

S=sum([abs(Ai) for Ai in A])
m=min([abs(Ai) for Ai in A])

if flag:
    print(S)
else:
    print(S-2*m)

Submission status: Accepted

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

if 0 in A:
  print(sum(absA))
  exit()

m=list(filter(lambda x:x<0,A))

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * N
    cnt = 0
    for i in range(N):
        if A[i] < 0:
            cnt += 1
        B[i] = abs(A[i])

    if cnt % 2 == 0:
        print(sum(B))
    else:
        print(sum(B) - 2 * min(B))

main()

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 = list(map(abs, A))
minmum = min(A_abs)

if cnt % 2 == 0:
    ans = sum(A_abs)
else:
    ans = sum(A_abs) - 2*minmum

print(ans)

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
    A[i] = abs(A[i])
if minus%2 == 0:
  print(sum(A))
else:
  print(sum(A)-(2*min(A)))

Submission status: Accepted

Solution code:
n = int(input())

counter = 0
a = 0
v = 10000000
for s in input().split():
    i = int(s)
    a += abs(i)
    if i < 0:
        counter += 1
    if abs(i) < v:
        v = abs(i)

if counter & 1:
    a -= v * 2
print(a)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
#アルゴリズム（動的計画法）で殴る解法
INF = float("inf")
dp = [[0,0] for _ in range(N+1)]
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])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
#偶数個しか正負反転できない
#小さい順に並べてマイナスは全部、境界は判定
S = sorted([[i,A[i]] for i in range(N)],key=lambda x: x[1])
judge = [False]*N
for j in range(0,N-1,2):
    if S[j][1]+S[j+1][1]<0:
        judge[S[j][0]] = True
        judge[S[j+1][0]] = True
for i in range(N-1):
    if judge[i]:
        A[i] *= -1
        A[i+1] *= -1
        judge[i+1] ^= True
print(sum(A))

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    negative = len([True for ai in a if ai <= 0])
    ans = sum([abs(ai) for ai in a])
    if negative % 2 == 0:
        print(ans)
    else:
        m = min([abs(ai) for ai in a])
        print(ans - m * 2)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
neg_num = 0
min_abs_a = float('inf')
sum_abs_A = 0
include_zero = False
for a in A:
  sum_abs_A += abs(a)
  min_abs_a = min(abs(a),min_abs_a)
  if a == 0: include_zero = True
  if a < 0 : neg_num += 1
print(sum_abs_A if neg_num%2==0 or include_zero is True else sum_abs_A - 2*min_abs_a)

Submission status: Accepted

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

negatives = len([a for a in A if a < 0])
if negatives % 2 == 0:
    m = 0
else:
    m = min(abs(a) for a in A)
print(sum(abs(a) for a in A) - 2 * m)

Submission status: Accepted

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

Submission status: Accepted

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

negativeCnt = 0
for a in A:
    if a < 0:
        negativeCnt += 1
A = list(map(lambda a: -a if a < 0 else a, A))
miniA = min(A)
if negativeCnt%2 == 0:
    print(sum(A))
else:
    print(sum(A)-2*miniA)

Submission status: Accepted

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

plusmax = A[0]+A[1]
minusmax = -A[0]-A[1]

for i in range(2,N):
    m1 = max(plusmax,minusmax)+A[i]
    m2 = max(plusmax-2*A[i-1],minusmax+2*A[i-1])-A[i]
    plusmax, minusmax = m1,m2

print(max(plusmax,minusmax))

Submission status: Accepted

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

Submission status: Accepted

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

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

odd_n = len([a for a in a_list if a < 0])

# 負の数の個数が偶数の場合は、全部正にできる
if odd_n % 2 == 0:
    s = 0
    for a in a_list:
        s += abs(a)
else:
    # 負の数の個数が奇数の場合は、0があったら全部正にできる
    # 0がない場合は、どれか1個が負のままで残るので、絶対値が一番小さいものを残す
    s = 0
    if 0 in a_list:
        for a in a_list:
            s += abs(a)
    else:
        min_abs = float('inf')
        for a in a_list:
            s += abs(a)
            min_abs = min(min_abs, abs(a))
        s -= min_abs * 2

ans = s
print(ans)

Submission status: Accepted

Solution code:
import sys

#+++++
		
def main():
	n = int(input())
	al = list(map(int, input().split()))
	
	k=[abs(x) for x in al]
	bb=min(k)
	ss=sum(k)
	cc=len([x for x in al if x < 0])%2
	ans = ss - bb * cc*2
	#print(ss,bb,cc)
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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


if 0 in lists:
    ans=0
    for _ in lists:
        ans+=abs(_)
    print(ans)
        #ok
    
    
else:
    abslists=[]
    for j in lists:
        abslists.append(abs(j))
        
    ans=0
    count=0
    
    for inner in lists:
        if inner<0:
            count+=1
        
        else:
            continue
            
    if count%2==0:
        for _ in lists:
            ans+=abs(_)
        print(ans)
        
    else:
        for _ in lists: 
            ans+=abs(_)  
        min1=min(abslists)
        print(ans-2*min1)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

# 負の数をカウントしつつ、絶対値が最小の数を求める & 0があるか
smallest = INF
minus = 0
is_zero = False
ans = 0
for a in A:
    smallest = min(smallest, abs(a))

    if a == 0:
        is_zero = True
    elif a < 0:
        minus += 1

    ans += abs(a)

if is_zero or minus % 2 == 0:
    print(ans)
else:
    ans -= smallest*2
    print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3
-10 5 -4"""
        output = """19"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """5
10 -4 -8 -11 3"""
        output = """30"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000"""
        output = """10000000000"""
        self.assertIO(input, output)
def resolve():
    N=int(input())
    A=[int(i) for i in input().split()]
    d2=sum([1 if i<0 else 0 for i in A])%2
    B=[abs(i) for i in A]
    bs=sum(B)
    if d2==0:
        print(bs)
    else:
        print(bs-2*min(B))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    dp = [[0,0] for i in range(N)]
    dp[0][0] = A[0]
    dp[0][1] = - A[0]
    for i in range(N-2):
        dp[i+1][0] = max(dp[i][0]+A[i+1],dp[i][1] - A[i+1])
        dp[i+1][1] = max(dp[i][0] - A[i+1],dp[i][1] + A[i+1])
    dp[N-1][0] = dp[N-2][0] + A[N-1]
    dp[N-1][1] = dp[N-2][1] - A[N-1]
    return max(dp[N-1])

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

Submission status: Accepted

Solution code:
# ABC125 D - Flipping Signs
N = int(input())
A = list(map(int,input().split()))

cnt = 0
is_zero = False
for i in range(N):
    if A[i] < 0:
        cnt += 1
    if A[i] == 0:
        is_zero = True

A = [abs(a) for a in A]

if cnt%2 == 0 or is_zero == True:
    print(sum(A))
else:
    print(sum(A)-2*min(A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappush,heappop

N = int(input())
array = list(map(int,input().split()))
nega = []
posi = []

for num in array:
  if num >= 0:
    heappush(posi,num)
  else:
    heappush(nega,num*(-1))


if len(nega)%2==0:
  ans = sum(nega) + sum(posi)
else:
  if len(nega)==N:
    max_nega = heappop(nega)
    ans = sum(nega) - max_nega
  else:
    min_posi = heappop(posi)
    max_nega = heappop(nega)
    if min_posi > max_nega:
      ans = sum(nega) + sum(posi) + min_posi - max_nega
    else:
      ans = sum(nega) + sum(posi) - min_posi + max_nega

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    if(len([i for i in A if i <= 0])%2):
        print(sum(map(abs,A))-2*min(map(abs,A)))
    else:
        print(sum(map(abs,A)))

    return

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
#!/usr/bin/env python3
plus,minus=[],[]
n=int(input())
m=10**9
for i in input().split():
    a = int(i)
    m=min(m,abs(a))
    if a>0:
        plus.append(a)
    else:
        minus.append(a)
if len(minus)%2==0:
    print(sum(plus)-sum(minus))
else:
    print(sum(plus)-sum(minus)-2*m)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

N=int(input())

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

count=0
mi=10**9
all=0

for i in range(N)[::-1]:
    mi=min(mi,abs(l[i]))
    if l[i]<0:
        count+=1
    elif l[i]==0:
        break

if count%2==1:
    print(sum(np.absolute(l))-2*mi)
else:
    print(sum(np.absolute(l)))

Submission status: Accepted

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

a.sort()

for i in range(0,n//2):
    if a[2*i] <= 0 and a[2*i+1] <=0:
        a[2*i] *= -1
        a[2*i+1] *= -1
    elif a[2*i] <= 0 and a[2*i+1] >=0:
        if abs(a[2*i]) > abs(a[2*i+1]):
            a[2*i] *= -1
            a[2*i+1] *= -1
    else:
        break
print(sum(a))

Submission status: Accepted

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

    count = 0
    ans = 0
    _min = 10**9

    for a in a_s:
        if a <= 0:
            count += 1
        ans += abs(a)
        _min = min(_min, abs(a))
    if count % 2 == 1:
        ans -= 2*_min
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A_list = list(map(int, input().split()))
ans = 0
dp = [[0, 0] for _ in range(n+1)]
dp[0][0] = 0
dp[0][1] = -float("inf")
for i in range(n-1):
    dp[i+1][0] = max(dp[i][0] + A_list[i], dp[i][1] - A_list[i])
    dp[i+1][1] = max(dp[i][0] - A_list[i], dp[i][1] + A_list[i])
dp[n][0] = max(dp[n-1][0] + A_list[n-1], dp[n-1][1] - A_list[n-1])
print(dp[n][0])

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]

check=False
minus=0
mini=float('inf')
total=0
for i in a:
    if i==0:
        check=True
    if i<0:
        minus+=1
    total+=abs(i)
    mini=min(mini,abs(i))


if minus%2==0:
    check=True

    
print(total if check else total-mini*2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 2019/09/18

n=int(input())
a=list(map(int,input().split()))
cnt=0
minus=0
suma=0
mina=float('inf')
for i in range(n):
    if a[i]<0:
        minus+=1
    suma+=abs(a[i])
    mina=min(mina,abs(a[i]))

ans=suma
if minus%2 and 0 not in a:
    ans-=mina*2
print(ans)

Submission status: Accepted

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

cnt = 0 # -の個数
minus = 10**9 # 絶対値が最小の数を入れる
ans = 0

for i in range(N):
    if A[i] < 0:
        cnt += 1
        minus = min(minus, -A[i])
        ans += -A[i]
    else:
        minus = min(minus, A[i])
        ans += A[i]

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, t = LI()
    print(b * (t // a))
    return

#B
def B():
    n = II()
    v = LI()
    c = LI()
    ans = 0
    for i in range(n):
        if v[i] > c[i]:
            ans += v[i] - c[i]
    print(ans)
    return

#C
def C():
    def gcd(a, b):
        if b > a: a, b = b, a
        while b:
            a, b = b, a % b
        return a
    n = II()
    a = LI()
    dp1 = [None] * (n - 1)
    dp1[0] = a[0]
    dp2 = [None] * (n - 1)
    dp2[-1] = a[-1]
    for i in range(1, n - 1):
        dp1[i] = gcd(dp1[i - 1], a[i])
        dp2[-i - 1] = gcd(dp2[-i], a[-i - 1])
    ans = 0
    dp1.insert(0, dp2[0])
    dp2.append(dp1[-1])
    for i in range(n):
        ans = max(ans, gcd(dp1[i], dp2[i]))
    print(ans)
    return

#D
def D():
    n = II()
    a = LI()
    positive = []
    negative = []
    for ai in a:
        if ai >= 0:
            positive.append(ai)
        else:
            negative.append(ai)
    positive.sort()
    negative.sort()
    ans = sum(positive) + sum(map(lambda x: abs(x), negative))
    if len(negative) & 1:
        ans -= 2 * min(positive[0] if positive else inf, abs(negative[-1]))
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(lambda n:abs(n), A))
C = list(filter(lambda n:n < 0, A))
if 0 in A:
    print(sum(B))
elif len(C) % 2 == 0:
    print(sum(B))
elif len(C) % 2 == 1:
    print(sum(B)-2*min(B))

Submission status: Accepted

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

total=0
mins=999999999999
mcnt=0

for i in range(N):
    total+=abs(A[i])
    if abs(A[i]) != A[i]:
        mcnt+=1
    if mins >= abs(A[i]):
        mins = abs(A[i])

if mcnt%2 == 0:
    print(total)
else:
    print(total - mins*2)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A_abs = [0]*N
for i in range(N):
    A_abs[i] = abs(A[i])

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

if minus_count == 0 or minus_count % 2 == 0:
    print(sum(A_abs))
else:
    print(sum(A_abs)-2*min(A_abs))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

def main():
    _ = int(input())
    A = list(map(int, input().split()))
    m = 0
    for i,a in enumerate(A):
        if a < 0:
            m += 1
        A[i] = abs(a)
    if m%2 == 1:
        print(sum(A)-min(A)*2)
    else:
        print(sum(A))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [[-float('inf'), -float('inf')] for _ in range(N + 1)]
dp[0][0] = 0

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 = len(list(filter(lambda x: x < 0, A)))

S = sum(map(abs, A))
if cnt % 2 == 0:
    print(S)
else:
    print(S - 2 * min(map(abs, A)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
li = list(map(int,input().split()))
sum = 0
pre = abs(li[0])
count = 0
zero = 0
for i in li:
    if i == 0:
        zero += 1
    if i < 0:
        count += 1
    sum += abs(i)
    if pre > abs(i):
        pre = abs(i)
if count%2 == 1 and zero == 0:
    print(sum-pre*2)
else:
    print(sum)

Submission status: Accepted

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

for i in range(n-1):
    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:
n=int(input())
r=list(map(int,input().split()))

result=0
negativeCount=0
minmumNumver=10**9

for item in r:
  if item<0:
    negativeCount+=1
    item=abs(item)

  result+=item
  minmumNumver=min(item,minmumNumver)

if negativeCount%2==1:

  result=result-minmumNumver*2
print(result)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort(key=lambda x: abs(x))
for x in A:
    if x < 0:
        count += 1
A = [abs(x) for x in A]
ans = 0
if count % 2 == 0:
    ans = sum(A)
else:
    ans = sum(A[1:]) - A[0]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,bisect,heapq

mod = 10**9+7

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(input())

def GCD(a,b):
    while(a%b != 0):
        a,b = b,a%b
    return b

def LCM(a,b):
    return a*b//GCD(a,b)

def main():
    N = I()
    A = LI()

    count_m = 0
    for a in A:
        if a < 0:
            count_m += 1
    A_abs = [abs(a) for a in A]

    if count_m %2 == 0:
        return(sum(A_abs))
    else:
        return(sum(A_abs)-2*(min(A_abs)))

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
arr=[]
for i in a:
    arr.append(abs(i))
neg=0
for i in a:
    if(i<0):
        neg+=1

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

Submission status: Accepted

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

s = sum(X)
count = 0
for a in A:
    if a < 0:
        count += 1

if count % 2 == 0:
    print(s)
else:
    print(s - 2 * min(X))

Submission status: Accepted

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

Submission status: Accepted

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

ct0 = 0
ctm = 0
minm = 100000000000000000
ans = 0

for i in range(n):
	if la[i] == 0:
		ct0 += 1
	elif la[i] < 0:
		ctm += 1
	
	m = abs(la[i])
	if m < minm:
		minm = m
	ans += m

if ct0 > 0 or ctm % 2 == 0:
	print(ans)
else:
	ans -= 2 * minm
	print(ans)

Submission status: Accepted

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

for i in A:
  if i==0:
    zero=1
  if i<0:
    minus+=1
#print(zero,minus)

A=list(map(abs,A))
if zero==1 or minus%2==0:
  print(sum(A))
else:
  print(sum(A)-2*min(A))

Submission status: Accepted

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

lb = [0]*(n+1)
lb_flip = [-100000000000000]*(n+1)

for i in range(n):
	lb[i+1] = max(lb[i]+la[i], lb_flip[i]-la[i])
	lb_flip[i+1] = max(lb[i]-la[i], lb_flip[i]+la[i])

#print(lb)
#print(lb_flip)

print(lb[n])

Submission status: Accepted

Solution code:
import numpy as np

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N=int(input())
A=np.array([int(i) for i in input().split()])
B=np.abs(A)
if np.sum(np.where(A<0,1,0)) % 2 == 1 :
    print(np.sum(B)-np.min(B)*2)
else:
    print(np.sum(B))

Submission status: Accepted

Solution code:
input()
A = [int(a) for a in input().split()]
abs_sum = sum(abs(a) for a in A)
if 0 in A:
    print(abs_sum)
    exit()

neg_count = sum(a < 0 for a in A)
print(abs_sum - (0 if neg_count % 2 == 0 else 2 * min(abs(a) for a in A)))

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:
    A[i]*=-1
    cnt+=1
A=list(map(abs, A))
A.sort()
if cnt&1==0:
  print(sum(A))
else:
  print(sum(A[1:])-A[0])

Submission status: Accepted

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

cnt = 0
m = 100000000000
ans = 0
for a in A:
    ans += abs(a)
    if a < 0:
        cnt += 1
    if abs(a) < m:
        m = abs(a)

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

Submission status: Accepted

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

abs_lis = [0] * N
count_neg = 0

for n in range(N):
    abs_lis[n] = abs(A[n])
ans = sum(abs_lis)
if 0 in A:
    print(ans)
else:
    for n in range(N):
        if A[n] < 0:
            count_neg += 1
    if count_neg % 2 == 1:
        print(ans - 2 * min(abs_lis))
    else:
        print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)


def solve_(N: int, A: "List[int]"):
    m = 1e10
    s = 0
    n_plus, n_minus = 0, 0
    for x in A:
        m = min(m, abs(x))
        if x >= 0:
            n_plus += 1
        else:
            n_minus += 1
        s += abs(x)
    # print(n_plus, n_minus)
    if n_minus % 2 == 0:
        print(s)
    else:
        print(s - m * 2)

    return


def solve(N: int, A: "List[int]"):
    inf = 1e10
    dp = [[-inf, -inf] for i in range(N + 1)]
    dp[0] = 0, -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])

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
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 = list(map(int, input().split()))

count = 0
m = 10**9
sum = 0
for i in a:
    if i < 0:
        count += 1
    i = abs(i)
    m = min(m,i)
    sum += i


if count % 2 == 1:
    sum -= m * 2

print(sum)

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

abs_a = list(map(abs, a))

if cnt % 2 == 0:
    print(sum(abs_a))
else:
    abs_a = list(map(abs, a))
    print(sum(abs_a) - 2 * min(abs_a))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)


def solve(N: int, A: "List[int]"):
    m = 1e10
    s = 0
    n_plus, n_minus = 0, 0
    for x in A:
        m = min(m, abs(x))
        if x >= 0:
            n_plus += 1
        else:
            n_minus += 1
        s += abs(x)
    # print(n_plus, n_minus)
    if n_minus % 2 == 0:
        print(s)
    else:
        print(s - m * 2)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
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 = list(map(int, input().split()))

cnt = 0
s = 0
m = 10**10
for i in range(n):
  if a[i] < 0:
    cnt += 1
  s += abs(a[i])
  m = min(m, abs(a[i]))

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    dp = [[0,0] for _ in range(n+1)]
    dp[0][0] = 0
    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[n][0])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

a = list(filter(lambda x: x < 0, As))
As = list(map(lambda x: abs(x), As))
As.sort()
if len(a) % 2 == 0:
    print(sum(As))
else:
    print(sum(As[1:]) - As[0])

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
b=False
sum=0
count=0
absmin=100000000000000
for i in l:
  if i==0:
    b=True
  elif i<0:
    count+=1
  if absmin>abs(i):
    absmin=abs(i)
  sum+=abs(i)
if b:
  print(sum)
else:
  if count%2==1:
    print(sum-2*absmin)
  else:
    print(sum)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
b=False
sum=0
count=0
absmin=10000000
for i in l:
  if i==0:
    b=True
  elif i<0:
    count+=1
  if absmin>abs(i):
    absmin=abs(i)
  sum+=abs(i)
if b:
  print(sum)
else:
  if count%2==1:
    print(sum-2*absmin)
  else:
    print(sum)