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.

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):

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')


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


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


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


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


if __name__ == '__main__':
    D()

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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()

Solution (Python):
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])

Solution (Python):
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)))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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())

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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


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

Solution (Python):
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[n])

Solution (Python):
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)))

Solution (Python):
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))

Solution (Python):
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)))

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

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)
    
    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




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


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):

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)
    
    if n_minus % 2 == 0:
        print(s)
    else:
        print(s - m * 2)

    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))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):

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])

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
sum = 0
neg = 0
neg_sum = 0
min = float('inf')
max = -float('inf')
for i in range(N):
	sum += A[i]
	if A[i] < 0:
		neg += 1
		neg_sum += A[i]
		if A[i] > max:
			max = A[i]
	else:
		if A[i] < min:
			min = A[i]
if neg % 2 == 1:
	if max + min < 0:
		neg_sum += min
	else:
		neg_sum -= max
print(sum - neg_sum * 2)

Solution (Python):
N = int(input())
x = [int(x) for x in input().split()]
dp = [[0 for _ in range(2)] for _ in range(N+1)]
dp[0][0] = 0
dp[0][1] = -10**9
for i in range(N):
  dp[i+1][0] = max(dp[i][0]+x[i],dp[i][1]-x[i])
  dp[i+1][1] = max(dp[i][0]-x[i],dp[i][1]+x[i])
print(dp[N][0])

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
tot = 0
for i in range(N):
    tot += abs(A[i])
if A.count(0)>0:
    print(tot)
else:
    cur = 0
    cnt = 0
    for i in range(N):
        if A[i]>0:
            c = i-cur
            if c%2==1:
                cnt += 1
            cur =i+1
    if A[-1]<0:
        c = N-cur
        if c%2==1:
            cnt += 1
    if cnt%2==0:
        print(tot)
    else:
        cmin = 10**10
        for i in range(N):
            cmin = min(cmin,abs(A[i]))
        print(tot-2*cmin)

Solution (Python):
from collections import Counter,defaultdict
import sys,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n = inp()
a = inpl()
m_cnt = 0
for i in range(n):
    if a[i] < 0:
        m_cnt += 1
        a[i] = abs(a[i])
a.sort()
if m_cnt%2:
    print(sum(a) - a[0]*2)
else:
    print(sum(a))

Solution (Python):
n, ct = int(input()), 0
l = list(map(int, input().split()))
for i, j in enumerate(l):
    if j < 0:
        ct += 1
        l[i] *= -1
l.sort()
if ct % 2:
    print(sum(l)-l[0]*2)
else:
    print(sum(l))

Solution (Python):
import numpy as np

n=int(input())
A=list(map(int,input().split()))
count=0
a_n=np.array(A)
abs_a=np.abs(a_n)
sum_a=np.sum(abs_a)
for x in A:
    if x<0:
        count+=1
if count%2==0:
    print(sum_a)
elif count%2==1:
    sum_b=sum_a-2*np.min(abs_a)
    print(sum_b)

Solution (Python):
N=int(input())
l=list(map(int,input().split()))
l2=sorted([num for num in l if num<0])
l3=sorted([num for num in l if num>=0])
if len(l2)%2==0:
  ans=sum([abs(n) for n in l])

elif l3!=[]:
  if abs(l2[-1]) < l3[0]:
    x=l2.pop()
  else:
    x=l3.pop(0)
  ans=sum([abs(n) for n in l2])+sum(l3)-abs(x)
else:
  x=l2.pop()
  ans=sum([abs(n) for n in l2])-abs(x)
print(ans)

Solution (Python):
N,*A=map(int,open(0).read().split())
x,y=0,-1e10
for a in A:x,y=max(x+a,y-a),max(x-a,y+a)
print(x)

Solution (Python):
N, *A = map(int, open(0).read().split())

x, y = 0, -10 ** 10
for a in A:
    x, y = max(x + a, y - a), max(x - a, y + a)
print(x)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
mc = 0
s = 0
m = float('inf')
for i in a:
  if i < 0:
    mc += 1
  s += abs(i)
  m = min(m, abs(i))
if mc % 2 == 0:
  print(s)
else:
  print(s -2 * m)

Solution (Python):
import numpy as np
N=int(input())
A = list(map(int, input().split()))


dp =[[0,0] for _ in range(len(A)+1) ]

dp[0][0] = A[0]
dp[0][1] = -A[0]

max_value= sum(A)
for y in range(len(A)-1):
    dp[y+1][0] = max(dp[y][0]+A[y+1], dp[y][1]-A[y+1])
    dp[y+1][1] = max(dp[y][1]+A[y+1], dp[y][0]-A[y+1]) 

print(dp[N-1][0])

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


if __name__ == '__main__':
    slove()

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

ans = 0
tmp = float('inf')
cnt = 0
for a in A:
    if a >= 0:
        ans += a
        tmp = min(tmp, a)
    else:
        ans -= a
        tmp = min(tmp, -a)
        cnt += 1
        
if cnt % 2 == 1:
    print(ans - tmp*2)
else:
    print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
dp = [[0]*2 for _ in range(n+1)]
dp[0][0] = 0
dp[0][1] = -10**10

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])

Solution (Python):
import numpy as np
n = int(input())
arr = list(map(int,input().split()))

odd = 0

for a in arr:
    if a < 0:
        odd += 1

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

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

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

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

cnt = 0
min = 10**9
total = 0

for i in A:
    total += abs(i)
    if abs(i) < min:
            min = abs(i)
    if i < 0:
        cnt += 1
if cnt%2 == 1:
    print(total - 2*min)
else:
    print(total)

Solution (Python):
n = int(input())
a = []
mc = 0

for x in input().split():
    i = int(x)
    if i < 0:
        mc += 1
        i = -i
    a.append(i) 


s = sum(a)
print(s if mc % 2 == 0 else s - min(a)*2)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a0 = [x for x in a if x<0]
a_abs = [abs(x) for x in a]
if len(a0)%2 == 0:
    ans = sum(a_abs)
else:
    ans = sum(a_abs) - 2 *min(a_abs)
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
ans = 0
m = abs(a[0])
for i in range(n-1):
    a1 = abs(a[i])
    ans += a1
    if a[i] < 0:
        a[i+1] = a[i+1]*(-1)
    if m > a1:
        m = a1
a1 = abs(a[n-1])
ans += a1
if a[n-1] >= 0:
    m = 0
else:
    if m > a1:
        m = a1
print(ans-2*m)

Solution (Python):
n = int(input())
lst = list(map(int, input().split()))

dp = [[0] * 2 for _ in range(n+1)]

dp[0][0] = 0
dp[0][1] = -10**10

i = 0
while i < n:
    dp[i+1][0] = max(dp[i][0] + lst[i], dp[i][1] - lst[i])
    dp[i+1][1] = max(dp[i][0] - lst[i], dp[i][1] + lst[i])
    i += 1

print(dp[n][0])

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

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

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

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

dp[0][0]=0
dp[0][1]=-3*10**9

for i in range(N-1):
	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(max(dp[-1][0]+A[-1], dp[-1][1]-A[-1]))

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

neg_count = 0
neg_candidate = abs(A[0])
for a in A:
    if a <= 0:
        neg_count += 1
    neg_candidate = min(neg_candidate, abs(a))

B = list(map(abs, A))

if neg_count % 2 == 0:
    print(sum(B))

else:
    print(sum(B)-2*neg_candidate)

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


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

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

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

_minus=0
for i in range(n):
    if a[i]<0:
        _minus+=1
abs_a = [abs(g) for g in a]

if _minus%2==0:
    print(sum(abs_a))
else:
    print(sum(abs_a) - 2*min(abs_a))

Solution (Python):
n = int(input())
an = [int(x) for x in input().split()]
abs_an = [abs(x) for x in an]

if len([x for x in an if x < 0])%2 == 0:
    print(sum(abs_an))
else:
    print(sum(abs_an)-2*min(abs_an))

Solution (Python):
import sys
input = sys.stdin.readline

import fractions 
sys.setrecursionlimit(1000000)

def main(): 

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

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    tmp = float("inf")
    S = 0
    count = 0
    for i in A:
        if tmp > abs(i):
            tmp = abs(i)
        if abs(i) != i:
            count += 1
        S += abs(i)
    if count%2 == 0:
        print(S)
    else:
        print(S-2*tmp)
    
main()

Solution (Python):
N=int(input())
A = [int(i) for i in input().split()]
cnt=0
ans=0
B=[]
C=[]
for i in range(N):
    B.append(abs(A[i]))
for i in range(N):
    if A[i]<0:
        C.append(A[i])
if len(C)%2==0:
    ans=sum(B)
    print(ans)
else:
    sel=min(B)
    print(sum(B)-2*abs(sel))

Solution (Python):
n=int(input())
alist = list(map(int, input().split()))

alist=sorted(alist)
ng=len(alist)
if alist[0]>=0:
    print(sum(alist))
else:
    now=0
    switch=0
    while now<ng and switch==0:
        if alist[now]<0:
            now+=1
        else:
            switch=1
    if now%2==1:
        hidari=now-1
        wa=0
        for al in alist:
            wa+=abs(al)
        if ng==hidari+1:
            wa-=abs(alist[hidari]*2)
        else:
            wa-=min(abs(alist[hidari]), abs(alist[hidari+1]))*2
        print(wa)
    else:
        hidari=now
        wa=0
        for al in alist:
            wa+=abs(al)
        print(wa)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


n = int(input())
a = [int(i) for i in readline().split()]

neg = len([i for i in a if i < 0])
if neg%2 == 0:
    ans = sum(abs(i) for i in a)
else:
    ans = sum(abs(i) for i in a) - 2*min(abs(i) for i in a)

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
absA = sorted([abs(A[i]) for i in range(N)], reverse = True)
minuscount = 0
for i in range(N):
  if A[i] < 0:
    minuscount += 1
if minuscount % 2 == 0:
  print(sum(absA))
else:
  print(sum(absA[: -1]) - absA[-1])

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline

def main():
	N = int(input())
	A = list(map(int,input().split()))
	A.sort()
	count = 0
	m = 10**10
	if 0 in A:
		A = np.array(A)
		print(sum(abs(A)))
	else:
		for i in range(N):
			if A[i]<0:
				count += 1
			m = min(m,abs(A[i]))
		A = np.array(A)
		if count%2 == 0:
			print(sum(abs(A)))
		else:
			print(sum(abs(A))-2*m)

if __name__ == "__main__":
	main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort()
for i in range(n//2):
	if a[i*2]<=0 and a[i*2+1]<=0:
		a[i*2]*=-1
		a[i*2+1]*=-1
for i in range(n-1):
	if a[i]<0 and a[i+1]<-a[i]:
		a[i]*=-1
		a[i+1]*=-1
print(sum(a))

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

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

m= [0]*n
d = 0
for i in range(n):
  m[i] = abs(l[i])
  if l[i] < 0:
    d += 1

if d%2 == 0:
  print(sum(m))
else:
  m.sort()
  print(sum(m)-2*m[0])

Solution (Python):
inf = 10**9
n = int(input())
lst = list(map(int,input().split()))
cnt = 0
m = inf
total = 0
for i in range(n):
    if lst[i] < 0:
        cnt += 1
    if abs(lst[i]) < m:
        m = abs(lst[i])
    total += abs(lst[i])
if cnt%2==0:
    print(total)
else:
    print(total - 2*m)

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

dp=[[0,0] for i in range(n)]

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

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

Solution (Python):
_ = input()
*A, = map(int, input().split())
N = [a for a in A if a < 1]
A = list(map(abs, A))
print(sum(A)-2*min(A)*(len(N)%2))

Solution (Python):
_ = input()
*A, = map(int, input().split())
N = [a for a in A if a < 1]
A = list(map(abs, A))
print(sum(A)-2*min(A)*(len(N)%2))

Solution (Python):
import numpy as np


def solve(a_list):
    negative_flag = False
    for a in a_list:
        if a < 0:
            negative_flag = not negative_flag

    
    sorted_list = sorted(np.abs(a_list), key=abs)
    if negative_flag:
        sorted_list[0] = -sorted_list[0]
    return sum(sorted_list)


def main():
    n = int(input())
    a_list = list(map(int, input().split()))

    ans = solve(a_list)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]

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

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])

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]
count = len([x for x in filter(lambda n: n<0, a)])
b = [x for x in map(abs, a)]

p = min(b)
q = sum(b)
if count % 2 != 0:
    ans = q - 2 * p
else:
    ans = q
print(ans)

Solution (Python):
N = int(input())
Alist = list(map(int,input().split()))

minabs = min(list(map(abs,Alist)))
sumabs = sum(list(map(abs,Alist)))

c_ne = 0
c_ze = 0
for i in range(N):
    if Alist[ i ] < 0:
        c_ne += 1
    if Alist[ i ] == 0:
        c_ze += 1

if c_ne % 2 == 0:
    print( sumabs )
elif c_ze > 0:
    print( sumabs )
else:
    print( sumabs - minabs * 2)

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

dp = [[[0] for j in range(2)] for i in range(N-1)]
dp[0][0] = sum(A)
A_ = A.copy()
A_[0] = A_[0]*-1
A_[1] = A_[1]*-1
dp[0][1] = sum(A_)

for i in range(1, N-1):
  dp[i][0] = max(dp[i-1][0],dp[i-1][1])
  cg1 = (A[i]+A[i+1])*2
  cg2 = (-A[i]+A[i+1])*2
  dp[i][1] = max(dp[i-1][0]-cg1,dp[i-1][1]-cg2)
  
print(max(dp[N-2][0],dp[N-2][1]))

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

Solution (Python):
n=int(input())
a=list(map(int, input().split()))
a_s=sorted(a)
for i in range(0,n-1,2):
    if a_s[i]<0 and a_s[i+1]<0:
        a_s[i]=-a_s[i]
        a_s[i+1]=-a_s[i+1]
    elif a_s[i]<0 and -a_s[i]>a_s[i+1]:
        a_s[i]=-a_s[i]
        a_s[i+1]=-a_s[i+1]
    else:
        break
print(sum(a_s))

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

count=0
total=0
min_=10**9
for i in range(n):
  total+=abs(a[i])
  if a[i]<0:
    count+=1
  if abs(a[i])<min_:
    min_=abs(a[i])
    
if count%2==0:
  print(total)
else:
  print(total-2*min_)

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    B = [abs(a) for a  in A]
    m = len([a for a in A if a < 0])
    if m % 2 == 0:
        print(sum(B))
    else:
        print(sum(B) - 2*min(B))
    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))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, A)

if __name__ == '__main__':
    main()

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

A_abs = [abs(i) for i in A]
A_abs_sum = sum(A_abs)
if 0 in A or len([i for i in A if i < 0]) % 2 == 0:
  print(A_abs_sum)
else:
  print(A_abs_sum - min(A_abs) * 2)

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

a_abs = [abs(i) for i in a]
a_abs_sum = sum(a_abs)
if 0 in a or len([i for i in a if i < 0]) % 2 == 0:
  print(a_abs_sum)
else:
  print(a_abs_sum - min(a_abs) * 2)

Solution (Python):

def main():
    
    
    
    N = int(input())
    A = tuple(map(int, input().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()