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

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

for i in range(1, N - 1):
    for j in range(2):
        if j == 0:
            dp[i][j] = max(dp[i-1][0] + A[i+1], dp[i-1][1] + A[i+1])
        else:
            dp[i][j] = max(dp[i-1][0] - 2 * A[i] - A[i+1], dp[i-1][1] + 2 * A[i] - A[i+1])

print(max(dp[N-2]))

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

n_neg = sum([1 for i in range(n) if a[i] < 0])
if n_neg%2 == 0:
    ans = sum([abs(aa) for aa in a])
else:
    min_abs = min([abs(aa) for aa in a])
    ans = sum([abs(aa) for aa in a]) - 2*min_abs
print(ans)

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

s = 0
c = 0
m = abs(a[0])
for i in range(n):
  t = abs(a[i])
  s += t
  if m > t:
    m = t
  if a[i] < 0:
    c += 1

if c % 2 == 1:
  s -= m * 2

print(s)

Solution (Python):



from collections import deque
import heapq
import math
import bisect


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

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

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


if __name__ == '__main__':
    main()

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

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

abs_a = list(map(abs, a[:]))
s = sum(abs_a[:])
m = len([i for i in a if i < 0])
if m % 2 == 0:
  print(s)
else:
  print(s - 2 * min(abs_a))

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

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

n = int(input())
x = list(map(int, input().split()))
mc = 0
m = 1000000001

for v in range(n):
    t = x[v]
    if t < 0:
        mc += 1
    
    m = min(m, abs(t))

if mc % 2 == 0:
    s = 0
    for v in range(n):
        s += abs(x[v])
    print(s)
else:
    s = 0
    for v in range(n):
        t = abs(x[v])
        if t == m:
            s -= t
        else:
            s += t
            
    print(s)

Solution (Python):
n = int(input())

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

if len([i for i in l if i < 0]) % 2 == 0:
  data = [abs(x) for x in l]
  print(sum(int(i) for i in data))
else:
  data = [abs(x) for x in l]
  print(sum(int(i) for i in data) - 2*min(data))

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

cnt = 0
min = 10000000000
for i in range(n):
    if x[i] < 0:
        cnt += 1
    if abs(x[i]) < min:
        min = abs(x[i])

if 0 in x:
    cnt = 0

ans = 0
for i in range(n):
    ans += abs(x[i])




if cnt % 2 == 0:
    print(ans)

else:
    print(ans - min*2)

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

Solution (Python):

import sys

def solve(N: int, A: "List[int]"):
    minus_count = 0
    
    for i in range(N):
        if A[i] < 0:
            minus_count += 1

    if minus_count % 2 == 0:
        result = sum([abs(x) for x in A])
    else:
        min_A = 10000000
        min_idx = -1
        for i, x in enumerate(A):
            if abs(x) < min_A:
                min_A = abs(x)
                min_idx = i
        result = 0
        for i, x in enumerate(A):
            if i == min_idx:
                result += abs(x) * -1
            else:
                result += abs(x)
    print(result)
    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())
As = list(map(int, input().split()))

has_zero = 0 in As
num_of_minus = len(list(filter(lambda x: x<0, As)))

abss = list(map(abs, As))
ans = sum(abss)
if num_of_minus%2 != 0:
    ans -= min(abss) * 2
    
print(ans)

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

a_sum = abs(a[0])
a_min = abs(a[0])
cnt = 0
if a[0] < 0:
    cnt += 1
for i in range(n - 1):
    a_min = min(a_min, abs(a[i+1]))
    a_sum += abs(a[i+1])
    if a[i + 1] < 0:
        cnt += 1
if cnt % 2 == 0:
    print(a_sum)
else:
    print(a_sum-a_min*2)

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

ans = sum(abs(ai) for ai in a)

if sum(ai < 0 for ai in a) % 2:
    ans -= 2 * min(abs(ai) for ai in a)

print(ans)

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

minus_cnt = len([i for i in a if i < 0])

a_abs = [abs(i) for i in a]
if minus_cnt%2 == 0:
  ans = sum(a_abs)
else:
  ans = sum(a_abs) - min(a_abs)*2
print(ans)

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

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

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

Solution (Python):
N=int(input())
A= [int(a) for a in input().split()]
minusnum=sum(a<0 for a in A)
ablist=[abs(a) for a in A]
ans=sum(ablist)
if minusnum%2:
    ans=ans-2*min(ablist)

print(ans)

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = [abs(i) for i in a]

counter = 0
for i in range(n):
    if a[i] < 0:
        counter += 1


if counter & 1 == 1:
    print(sum(b) - min(b) * 2)
else:
    print(sum(b))

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

cnt = len([1 for i in range(N) if A[i] < 0])
SUM = sum(map(abs,A))
MIN = min(map(abs,A))

if cnt%2 == 0:
    print(SUM)
else:
    print(SUM-2*MIN)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
B = [i if i > 0 else i * -1 for i in A]
c = 0
s = 0
for j in A:
    if j < 0:c += 1
if c % 2 == 0:
    s = sum(B)
else:
    s = sum(B) - min(B) * 2
print(s)

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

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
cnt = 0
allsei = False
for i in range(n):
    if a[i] == 0:
        allsei = True
        break
    if a[i] < 0:
        cnt += 1
if cnt%2 == 0:
    allsei = True

ans = 0
mini =12345678901
for i in range(n):
    ans += abs(a[i])
    mini = min(mini,abs(a[i]))
if not allsei:
    ans -= 2*mini
print(ans)

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

min_abs = 10 ** 9 + 1
sum_abs = 0
cnt_neg = 0
for i in range(n):
  a_abs = a[i] if a[i] > 0 else - a[i]
  sum_abs += a_abs
  min_abs = min(min_abs, a_abs)
  if a[i] < 0:
    cnt_neg += 1
if cnt_neg % 2:
  print(sum_abs - 2 * min_abs)
else:
  print(sum_abs)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
total = 0
X = [0]*N
flag = False
subcount = 0

for i in range(N):
    if A[i] == 0:
        flag = True
    elif A[i] < 0:
        subcount += 1
    X[i] = abs(A[i])
    total += X[i]

if flag or (subcount % 2 == 0):
    print(total)
else:
    print(total-2*min(X))

Solution (Python):
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [abs(i) for i in a]
b.sort()

i = bisect_left(a, 0)
if i % 2==0:
    print(sum(b))
else:
    print(sum(b) - 2*b[0])

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

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

n=0
sm=0
if A[0]>0:
  mn=A[0]
else:
  mn=(-1)*A[0]


for i in range(0,N):
  if A[i]<0:
    n=n+1
    sm=sm-A[i]
    if (-1)*A[i]<mn:
      mn=(-1)*A[i]
  else:
    sm=sm+A[i]
    if A[i]<mn:
      mn=A[i]
if n%2==0:
  print(sm)
else:
  print(sm-2*mn)

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

minus_count = 0
max_minus = -1145141919
min_plus = 1145141919
ans = 0
for a in A:
    ans += abs(a)
    if a < 0:
        minus_count += 1
        if max_minus < a:
            max_minus = a
    else:
        if min_plus > a:
            min_plus = a

if minus_count % 2 == 1:
    if -min_plus < max_minus:
        ans += 2*max_minus
    else:
        ans += -2*min_plus

print(ans)

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

minus = []
plus = []

for i in a:
    if i < 0:
        minus.append(i)
    else:
        plus.append(i)
plus.sort()
minus.sort(reverse=True)

if len(plus)==0:
    if len(minus)%2==0:
        print(-sum(minus))
    else:
        print(-sum(minus)+2*minus[0])
    exit()

if len(minus)==0:
    print(sum(a))
    exit()

if len(minus) % 2==0:
    print(sum(plus) - sum(minus))
    exit()

if - minus[0] < plus[0]:
    print(sum(plus) - sum(minus) +2*minus[0])
else:
    print(sum(plus) - sum(minus) -2*plus[0])

Solution (Python):
n = int(input())
A = list(int(i) for i in (input().split()))

cnt = 0
tmp_sum = 0
minimum = 1000000000
for i in range(n):
  if(A[i] <= 0):
    cnt += 1
    tmp_sum = tmp_sum - A[i]
    if(minimum > A[i] * (-1)):
      minimum = A[i] * (-1)
  elif(A[i] > 0):
    tmp_sum = tmp_sum + A[i]
    if(minimum > A[i]):
      minimum = A[i]
if((cnt % 2) == 1):
  sum = tmp_sum - minimum * 2
else:
  sum = tmp_sum
print(sum)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
answer = 0
tmp = abs(a[0])
check = 0

for b in a:
    if b == 0:
        check += 1
        tmp = 0
    else:
        if b < 0:
            check += 1
        b = abs(b)
        if b < tmp:
            tmp = b
            answer += tmp
        else:
            answer += b
if check % 2 == 1:
    answer -= 2*tmp
print(answer)

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



num_minus = 0
for i in A:
    if i < 0:
        num_minus +=  1
        
A_abs = [abs(i) for i in A]
if num_minus % 2 == 0:
    print(sum(A_abs))
else:
    print(sum(A_abs)- 2*min(A_abs))

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

i = 0
while i < n - 1:
    if a[i] <= 0:
        a[i] *= -1
        a[i+1] *= -1
    i += 1

s_a = sorted(a)

if s_a[0] < 0 and abs(s_a[0]) > s_a[1]:
    s_a[0] *= -1
    s_a[1] *= -1
    print(sum(s_a))
else:
    print(sum(s_a))

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

dp =[[0, -10**9]]


for i in range(1,n+1):
	dp.append([max(dp[i-1][0]+ai[i-1], dp[i-1][1]-ai[i-1]), \
			max(dp[i-1][0]-ai[i-1], dp[i-1][1]+ai[i-1])])
	
    
print(dp[n][0])

Solution (Python):
N = int(input().strip())
A= [int(x) for x in input().strip().split(" ")]

minus_list = filter(lambda x: x<0,A)
minus_cnt = len(list(minus_list))

abs_list = list(map(abs,A))

if minus_cnt % 2 == 0:
    print(sum(abs_list))
else:
    print(sum(abs_list) - 2* min(abs_list))

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
B=[abs(i) for i in A]
minus=0
for i in A:
    if i<0:
        minus+=1
if minus%2==0:
    print(sum(B))
else:
    print(sum(B)-2*min(B))

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

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

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

count = 0
absmin = abs(A[0])

for i in range(n):
  if A[i] < 0:
    count += 1
    A[i] = - A[i]
  if A[i] < absmin:
    absmin = A[i]

if count % 2 == 0:
  print(sum(A))
else:
  print(sum(A) - 2 * absmin)

Solution (Python):

from sys import stdin
import numpy as np



s_in = lambda: stdin.readline()[:-1]  
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


N = d_in()
A_list = np.array(ds_in())
abs_A = np.abs(A_list)

ans = abs_A.sum()

if (A_list < 0).sum() % 2 == 0:
    print(ans)
else:
    print(ans - min(abs_A)*2)

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


minuscount = 0
abss = []
for i in a:
	abss.append(abs(i))
	if (i < 0):
		minuscount += 1

if minuscount % 2 == 0:
	print (sum(abss))
else :
	print (sum(abss) - 2 * min(abss))

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

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
B = [abs(x) for x in A]

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


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

Solution (Python):
import numpy as np

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

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

ans = 0
j = 0
B = list(map(abs,A))

for a in A:
    if a <= 0:
        j += 1
ans = sum(B)
if j%2 == 1:
    k = min(B)
    ans -= 2*k
print(ans)

Solution (Python):
input()
a = [int(i) for i in input().split()]
print(sum(map(lambda x:abs(x), a))-(0 if sum(map(lambda x:1 if x < 0 else 0, a))%2==0 else 2)*(min(map(lambda x:abs(x), a))))

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

ans = 0
j = 0
B = list(map(abs,A))

for a in A:
    if a < 0:
        j += 1
ans = sum(B)
if j%2 == 1:
    k = min(B)
    ans -= 2*k
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
abs_sum = 0
abs_min = 10 ** 10
minus_count = 0
for i in range(N):
    if A[i] < 0:
        minus_count += 1
    a_abs = abs(A[i])
    abs_sum += a_abs
    abs_min = min(abs_min, a_abs)
if minus_count % 2 == 0:
    print(abs_sum)
else:
    print(abs_sum - abs_min * 2)

Solution (Python):



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

total = 0
minus = 0
minimum = abs(a[0])

for v in a:
        total += abs(v)
        if v < 0 :
                minus += 1
        if abs(v) < minimum:
                minimum = abs(v)

if minus%2 is 1:
        total -= minimum*2

print(total)

Solution (Python):
import bisect

n = int(input())
a = sorted(list(map(int, input().split())))
i = bisect.bisect_left(a,0)
if i % 2 == 0:
    ans = abs(sum(a[:i]))+sum(a[i:])
else:
    if i == n:
        ans = abs(sum(a[:i-1]))+a[i-1]
    else:
        ans = abs(sum(a[:i-1]))+abs(a[i]+a[i-1])+sum(a[i+1:])
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
cnt = 0
ans = 0
min_ = 10**9+1
for a in A:
    if a < 0:
        cnt += 1
    min_ = min(min_, abs(a))
    ans += abs(a)
if cnt %2 == 1:
    ans -= 2*min_
print(ans)

Solution (Python):
from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math

import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))

def unite(x, y):
    
    x = root(x)
    y = root(y)
    if x == y:
        return
    
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  
        return x
    else:
        node[x] = root(node[x])  
        return node[x]

n, a = II(), LI()
a_abs = list(map(abs,a))
print(sum(a_abs)) if sum(x < 0 for x in a) % 2 == 0 else print(sum(a_abs) - 2 * min(a_abs))

Solution (Python):
from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math

import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))

def unite(x, y):
    
    x = root(x)
    y = root(y)
    if x == y:
        return
    
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  
        return x
    else:
        node[x] = root(node[x])  
        return node[x]

n, a = II(), LI()
a_abs = [abs(i) for i in a]
print(sum(a_abs)) if sum(x < 0 for x in a) % 2 == 0 else print(sum(a_abs) - 2 * min(a_abs))

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

under_zero_count = sum([i < 0 for i in A])

ans = 0
if under_zero_count % 2 == 0:
    for i in range(N):
        ans += abs(A[i])
    print(ans)
else:
    abs_list = []
    for i in range(N):
        abs_list.append(abs(A[i]))
    print(sum(abs_list) - min(abs_list)*2)

Solution (Python):
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
A_abs = [abs(x) for x in A]

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

res = 0

if minus_cnt % 2 == 0:
    res = sum(A_abs)
else:
    res = sum(A_abs) - 2*min(A_abs)

print(res)

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

absAList = [abs(i) for i in AList]
ans = sum(absAList)
if len([i for i in AList if i < 0]) % 2 == 1:
    ans -= min(absAList) * 2

print(ans)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
dp = [[0 for i in range(2)] 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])

Solution (Python):
n = int(input())
a = map(int,input().split())
alists = []
num = 0

for i in a:
    alists.append(abs(i))
    if i < 0:
        num = num + 1
        
if num % 2 == 1:
    print(sum(alists)-min(alists)*2)
else:
    print(sum(alists))

Solution (Python):


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

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

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

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
b=[i for i in a if i<1]
ans=0;k=0
if len(b)%2==0:
    for i in a:ans+=abs(i)
else:
  c=sorted([abs(i) for i in a]);l=c[0]
  for i in a:
    if (i==l or i==-l) and k==0:
      ans=ans+l if l<0 else ans-l
      k+=1
    else:
      ans+=abs(i)
print(ans)

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

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

Solution (Python):
x = int(input())
y = list(map(int, input().split(" ")))

for i in range(x - 1):
  if y[i] < 0:
    y[i] *=-1
    y[i + 1] *=-1

if y[-1] < 0 and abs(min(y[0:-1])) < abs(y[-1]) :
  y[-1] *= -1
  y[y.index(min(y[0:-1]))] *= -1

print(sum(y))

Solution (Python):
import numpy
from operator import add
from functools import reduce

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

minus_num = 0
abs_A = []
for a in A:
    if a < 0:
        minus_num += 1
    abs_A.append(numpy.abs(a))

if minus_num % 2 == 0:
    print(reduce(add, abs_A))
else:
    abs_A.sort()
    print(reduce(add, abs_A[1:])-abs_A[0])

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

Solution (Python):

import sys

import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

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

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

Solution (Python):

import sys

import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

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] = float('inf') * -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=list(map(int,input().split()))
n_minus=sum([a<0 for a in A])
abs_A=[abs(a) for a in A]
ans=sum(abs_A)
if n_minus%2==0:
        print(ans)
else:
        print(ans-2*min(abs_A))

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

neg_cnt = 0
for a in A:
  if a < 0:
    neg_cnt += 1

B = list(map(abs, A))
if neg_cnt%2 == 0:
  print(sum(B))
else:
  print(sum(B) - 2*min(B))

Solution (Python):
import numpy as np

inf = float('inf')

N = int(input())
a = map(int, input().split())

dp = np.empty((N + 1, 2))
dp[0][0] = 0
dp[0][1] = -inf



for i, aa in enumerate(a, 0):
    dp[i + 1][0] = max(dp[i][0] + aa, dp[i][1] - aa)
    dp[i + 1][1] = max(dp[i][0] - aa, dp[i][1] + aa)
print(int(dp[N][0]))

Solution (Python):
import numpy as np

inf = float('inf')

N = int(input())
a = map(int, input().split())

dp = np.zeros((N + 1, 2))
dp[0][1] = -inf



for i, aa in enumerate(a, 0):
    dp[i + 1][0] = max(dp[i][0] + aa, dp[i][1] - aa)
    dp[i + 1][1] = max(dp[i][0] - aa, dp[i][1] + aa)
print(int(dp[N][0]))

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

dp0 = [0] * N
dp1 = [0] * N
dp0[0] = a[0]
dp1[0] = -(10 ** 10)
for i in range(1, N):
    dp0[i] = max(dp0[i - 1] + a[i], dp1[i - 1] + a[i])
    dp1[i] = max(dp0[i - 1] - 2 * a[i - 1] - a[i], dp1[i - 1] + 2 * a[i - 1] - a[i])

print(max(dp0[N - 1], dp1[N - 1]))

Solution (Python):
n=int(input())
a_n=list(map(int,input().split()))
count=0
ans=0
for i in a_n:
  if i <0:
    count +=1

def fun():
  tmp_ans=0
  for i in a_n:
    if i<0:
      tmp_ans += -1*i
    else:
      tmp_ans += i
  return tmp_ans

if count%2==0:
  ans = fun()
else:
  tmp=abs(a_n[0])
  for i in a_n:
    if tmp > abs(i):
      tmp = abs(i)
  
  ans =fun()-2*tmp
print(ans)

Solution (Python):
n=int(input())
a_n=list(map(int,input().split()))
count=0
ans=0
for i in a_n:
  if i <0:
    count +=1

if count%2==0:
  for i in a_n:
    if i<0:
      ans += -1*i
    else:
      ans += i
else:
  tmp=abs(a_n[0])
  for i in a_n:
    if tmp > abs(i):
      tmp = abs(i)
  for i in a_n:
    if i <0:
      ans +=-1*i
    else:
      ans +=i
  ans -=2*tmp
print(ans)

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]
ans=0
m=100000000000
p=0
for i in a:
    if i<0:
        p+=1
    m=min(m,abs(i))
    ans+=abs(i)

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

Solution (Python):
from functools import reduce
import math

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N = int(input())
    A = list(int(_) for _ in input().split())
    min_cnt = 0
    for i in range(N):
        if A[i] < 0:
            min_cnt +=1
        A[i] = abs(A[i])
    if min_cnt % 2 ==0:
        ans = sum(A)
    else:
        ans = sum(A)-2*(min(A))
    print(ans)
    
if __name__ == '__main__':
    main()

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

A_m = list()
A_p = list()
for a in A:
    if a >= 0: A_p.append(a)
    else: A_m.append(a)
M = 0
M += sum(A_p)
M -= sum(A_m)
if len(A_m)%2:
    A_abs = list(map(abs, A))
    M = sum(A_abs)
    M -= 2*min(A_abs)
print(M)

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

f = False
n = 0

for i in range(N):
    if A[i] == 0:
        f = True
    elif A[i] < 0:
        n += 1
        A[i] = abs(A[i])

ans = 0
for i in A:
    ans += i

if f:
    print(ans)
elif n % 2 == 0:
    print(ans)
elif n % 2 == 1:
    print(ans - 2 * min(A))

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
S = 0
temp = 0
flg = False

for i in A:
    S += abs(i)
    if i < 0:
        temp += 1
    if i == 0:
        flg = True

if temp % 2 == 0 or flg is True:
    print(S)
else:
    print(S - 2*min([abs(y) for y in A]))

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    total = 0
    mn = float('inf')
    cnt = 0
    for a in A:
        if a < 0:
            cnt += 1
        mn = min(mn, abs(a))
        total += abs(a)
    if cnt % 2 != 0:
        total -= mn * 2
    print(total)
    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
flag = False
l = [abs(i) for i in A]
if 0 in A:
  pass
else:
  for j in A:
    if j < 0:
      count += 1
  if count % 2 == 0:
    pass
  else:
    flag = True
    
if flag:
  print(sum(l)-min(l)*2)
else:
  print(sum(l))

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

minus_cnt = 0
abs_min = float('inf')
abs_sum = 0
for ai in a:
    if ai<0:
        minus_cnt += 1
    abs_min = min(abs_min, abs(ai))
    abs_sum += abs(ai)

if minus_cnt%2==0:
    print(abs_sum)
else:
    print(abs_sum - 2*abs_min)

Solution (Python):


import sys
input = sys.stdin.readline

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



dp = [[0, 0] for _ in range(N)]

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

for i in range(N - 1):
    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])

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

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

abs_sum = sum(abs(a) for a in A)
if sum(a < 0 for a in A) %2 == 0:
    print(abs_sum)
    exit(0)
abs_min = min(abs(a) for a in A)

print(abs_sum - 2*abs_min)

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
dp = [[0, 0] for _ in range(N-1)]
dp[0][0] = A[0] + A[1]
dp[0][1] = -dp[0][0]

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

print(max(dp[-1]))

Solution (Python):
import sys
input=sys.stdin.readline
N=int(input())
num = list(map(int,input().split()))
c=0
ans=0
for i in range(N):
  if num[i]<0:
    c+=1 
ans = list(map(lambda x: abs(x),num))
if c%2==0:
  print(sum(ans))
else:
  print(sum(ans) - min(ans,key=lambda x: abs(x))*2)

Solution (Python):
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
N = ni()
A = na()
minas=0
tmp=10**9
for i in range(N):
    tmp = min(tmp,abs(A[i]))
    if(A[i]<0):
        minas +=1
        A[i]=-A[i]


if(minas%2==1):
    
    print(sum(A)-2*tmp)
else:
    print(sum(A))

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

Solution (Python):


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

cnt = 0
abs_A = []
for i in range(N):
    if A[i] < 0:
        cnt += 1
        abs_A.append(-A[i])
    else:
        abs_A.append(A[i])
ans = sum(abs_A)
if cnt % 2 != 0:
    ans -= 2*min(abs_A)

print(ans)

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

count = sum([a < 0 for a in A])
abss = [abs(a) for a in A]

if count % 2 == 0:
    print(sum(abss))
else:
    print(sum(abss) - min(abss)*2)

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

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
ans = 0
res = 0
flag = 0
for i in range(len(A)):
    if A[i]<0:
        res += 1
        A[i] *= -1
    elif A[i] == 0:
        flag = 1
if res%2 == 1 and flag != 1:
    print(sum(A) - min(A)*2)
else:
    print(sum(A))

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