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):
def main():
	N = int(input())
	A= list(map(int, input().split()))
	pos = []
	neg = []
	ans = 0
	min_neg = 10**9
	min_pos = 10**9
	for i in range(N):
		if A[i] > 0:
			pos.append(A[i])
			min_pos = min(min_pos, A[i])
		else:
			neg.append(-A[i])
			min_neg = min(min_neg, -A[i])
	ans = sum(neg)+sum(pos)
	if len(neg)%2 == 1:
		ans -= 2*min(min_pos, min_neg) 
	print(ans)


if __name__ == '__main__':
    main()

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

B = [0]*N
S = 0
cnt = 0
flag = False
for i in range(N):
    if A[i]>0:
        B[i] = A[i]
        S += B[i]
    elif A[i]<0:
        B[i] = -A[i]
        S += B[i]
        cnt += 1
    else:
        flag = True
if cnt%2==0 or flag:
    print(S)
else:
    print(S-2*min(B[i] for i in range(N)))

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

Solution (Python):
import sys
import numpy as np;
sys.stdin.readline()
a=np.array(sys.stdin.readline()[:-1].split(),dtype=np.int64)
b=np.abs(a)
print(np.sum(b)-((np.sum(np.sign(a)<0)%2)>0)*2*np.min(b))

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

dp = np.zeros((N+1, 2), dtype=int)
dp[0, 1] = -10**9

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().strip())
A = list(map(int, input().strip().split(' ')))
_A = [abs(a) for a in A]
if len([1 for a in A if a < 0]) % 2 == 0:
  print(sum(_A))
else:
  _A = sorted(_A)
  print(sum(_A[1:])-_A[0])

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):
N = int(input())
A = []
neg = 0
for i in map(int,input().split()):
    if i < 0:
        A.append(-i)
        neg += 1
    else:
        A.append(i)
ans = 0
if neg % 2 == 0:
    ans = sum(A)
else:
    ans = sum(A) - 2 * min(A)
print(ans)

Solution (Python):
from sys import stdin

INF = 10 ** 16

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

"""
dp[i][j]を j=1 ならiを選んで反転した場合（すなわち A_i+1 の符号が反転している状態）
の A_1, A_2, ... , A_i の最大値として定義する

今反転しない & 前の状態（反転してない or 反転した）
今反転する & 前の状態（反転してない or 反転した）
といったような4状態から最大値をみつけていく感じ
"""
dp = [[None] * 2 for _ in range(N+10)]

dp[0][0] = 0
dp[0][1] = -INF 

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

    
    
    
    dp[i+1][1] = max(dp[i][0]-A[i], dp[i][1]+A[i])






print(dp[N][0])

Solution (Python):
import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = A.copy()
B.sort()
C=[]
for i in range(N):
  if B[i]<0:
    C.append(B[i])
  else:
    continue
count = len(C)
if count % 2 == 0:
  B = np.abs(B)
  ans = sum(B)
else:
  B = np.abs(B)
  X = sum(B)
  ans = X - 2*min(B)
print(ans)

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

sc = 0
wmin = int(1e10)

for a in A:
  if a < 0:
    sc += 1
  wmin = min(wmin, abs(a))
  
ans = sum(B) if sc%2 == 0 else sum(B) - 2*wmin
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(1000000)

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

rcd = dict()


def dp(pos, sign):

    
    if pos == N-1:
        if sign == 0:
            return A[pos]
        else:
            return -A[pos]

    
    if (pos, sign) in rcd:
        return rcd[(pos, sign)]

    elif sign == 0:
        
        rcd[(pos, sign)] = max( dp(pos+1, 0) + A[pos], dp(pos+1, 1) - A[pos])
        return rcd[(pos, sign)]

    else: 
        
        rcd[(pos, sign)] = max( dp(pos+1, 0) -  A[pos], dp(pos + 1, 1) + A[pos])
        return rcd[(pos, sign)]

print '{}'.format( dp(0,0) )

Solution (Python):



import sys
sys.setrecursionlimit(1000000)

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

visit = dict()

def dp(pos, sign):
    
    if pos == N-1:
        if sign == 0:
            return A[pos]
        else:
            return -A[pos]

    if (pos, sign) in visit:
        return visit[(pos, sign)]

    elif sign == 0:
        
        visit[(pos, sign)] = max( dp(pos+1, 0) + A[pos], dp(pos+1, 1) - A[pos])
        return visit[(pos, sign)]

    else: 
        
        visit[(pos, sign)] = max( dp(pos+1, 0) -  A[pos], dp(pos + 1, 1) + A[pos])
        return visit[(pos, sign)]

print '{}'.format( dp(0,0) )

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

class Solution():
    def dp(self, pos, sign):
        if pos == self.n-1:
            if sign == 0:
                return +self.lst[pos]
            else:
                return -self.lst[pos]
        elif (pos, sign) in self.vis:
            return self.rcd[pos][sign]
        elif sign == 0:
            self.rcd[pos][sign] = max(self.dp(pos+1, 0) + self.lst[pos], self.dp(pos+1, 1) - self.lst[pos])
            self.vis.add((pos, sign))
            return self.rcd[pos][sign]
        else:
            self.rcd[pos][sign] = max(self.dp(pos+1, 0) - self.lst[pos], self.dp(pos+1, 1) + self.lst[pos])
            self.vis.add((pos, sign))
            return self.rcd[pos][sign]

    def run(self):
        self.n = int(input())
        self.lst = list(map(int, raw_input().split()))
        self.rcd = [[0, 0] for _ in range(self.n)]
        self.vis = set()
        print(self.dp(0, 0))

solution = Solution()
solution.run()

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

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

abs_total = 0
n_count = 0
min_abs_a = 10**9
for A in An:
    a = abs(A)
    abs_total += a
    if a < min_abs_a:
        min_abs_a = a
    if A <= 0:
        n_count += 1
if n_count%2 == 1:
    abs_total -= min_abs_a*2
print(abs_total)

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

flg = 1
ans = 0
mini = float("inf")
for a in A:
  if a < 0:
    flg *= -1
  elif a == 0:
    flg = 0
  ans += abs(a)
  mini = min(abs(a),mini)

if flg == -1:
  ans -= 2* mini
print(ans)

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

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

a=np.array(a)
a=np.abs(a)
a=np.sort(a)
goukei=0

if mynas % 2 ==0:
    for j in range(n):
        goukei += a[j]
else:
    for k in range(n):
        goukei+=a[k]
    goukei-=a[0]*2

print(goukei)

Solution (Python):

N = int(input())
A = list(map(int, input().split()))
dp = [[0, 0] for i in range(N+1)]
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):
n = int(input())
a = list(map(int, input().split()))
new_a = []
sum = 0
minus_count = 0

for i in range(n):
	new_a.append(abs(a[i]))

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

if minus_count % 2 == 0:
	for i in range(n):
		sum += abs(a[i])
else:
	for i in range(n):
		sum += new_a[i]
	sum = sum - min(new_a) * 2

print(sum)

Solution (Python):


import sys
import copy

sys.setrecursionlimit(1000000)





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

sumV = 0
for x in A:
    sumV += abs(x)

minus = sum(x < 0 for x in A)

if A.count(0) or minus % 2 == 0:
    print(sumV)
    exit()

minV = 1e15
for x in A:
    minV = min(minV, abs(x))

print(sumV - 2 * minV)

Solution (Python):



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

ng_cnt = 0

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

if ng_cnt % 2 == 0:
    print '{}'.format( sum(A) )
else:
    print '{}'.format( sum(A) - min(A)*2)

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

Solution (Python):



def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = []
    dp.append([0, -10**9-1])

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

    
    ans = dp[N][0]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def solve(N, A):
    if len(list(filter(lambda x: x < 0, A))) % 2 == 0:
        return sum(map(abs, A))
    else:
        min_abs = min(map(abs, A))
        return sum(map(abs, A)) - 2 * min_abs


def solve_dp(N, A):
    """
    >>> N = 3
    >>> A = [-10, 5, -4]
    >>> solve_dp(N, A)
    19
    >>> N = 5
    >>> A = [10, -4, -8, -11, 3]
    >>> solve_dp(N, A)
    30
    """
    
    
    

    
    dp = [[None, None] for _ in range(N)]
    for i in range(N - 1):
        if i == 0:
            dp[0][0] = A[0]
            dp[0][1] = -A[0]
            continue
        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])
    
    return max(dp[N - 2][0] + A[N - 1], dp[N - 2][1] - A[N - 1])





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

Solution (Python):


import sys
import math
 
 
N = int(input())
An = list(map(int, sys.stdin.readline().rstrip().split()))
 
ans = 0
mn = 10**9
minus = 0
for a in An:
  mn = min(mn, abs(a))
  ans += abs(a)
  if a < 0:
    minus += 1
 
if minus%2 == 0:
  print(ans)
else:
  print(ans-mn*2)

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

def solveDp():
    POS, NEG = 0, 1
    dp = [[0 for _ in range(n + 1)] for _ in range(2)]
    dp[NEG][0] = -float('inf')
    for i in range(n):
        dp[POS][i + 1] = max(dp[POS][i] + a[i], dp[NEG][i] - a[i])
        dp[NEG][i + 1] = max(dp[POS][i] - a[i], dp[NEG][i] + a[i])
    print(dp[POS][n])

def solve():
    nNegative = 0
    total = 0
    minVal = float('inf')
    for num in a:
        if num < 0:
            num *= -1
            nNegative += 1
        minVal = min(minVal, num)
        total += num
    print(total if nNegative & 1 == 0 else total - 2 * minVal)

solveDp()

Solution (Python):
def solve(N, A):
    if len(list(filter(lambda x: x < 0, A))) % 2 == 0:
        return sum(map(abs, A))
    else:
        min_abs = min(map(abs, A))
        return sum(map(abs, A)) - 2 * min_abs


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

Solution (Python):
N = int(input())
aa = list(map(int, input().split()))
abs_sum = sum(map(abs, aa))
if 0 in aa:
    print(abs_sum)
    exit()
now = aa[-1]
for i in range(1, N):
    now = -aa[N-1-i] if now < 0 else aa[N-1-i]
if now < 0:
    print(abs_sum - 2 * min(map(abs, aa)))
else:
    print(abs_sum)

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


if __name__ == "__main__":
    main()

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

cnt = 0
min_val = abs(a[0])
for it in a:
    if abs(it) < min_val:
        min_val = abs(it)
    
    if it < 0:
        cnt+=1
        
abs_list = list(map(abs, a))
if cnt%2 == 0:
    print(sum(abs_list))
else:
    print(sum(abs_list) - 2*min_val)

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

sum = 0
m = 1e10  
negativeCount = 0
for i in range(N):
    sum += abs(A[i])
    m = min(m, abs(A[i]))
    if A[i] < 0:
        negativeCount += 1

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

print(sum)

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

dp = [[0] * 2 for i in range(n)]
dp[0] = [a[0], -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):


import sys
import math


N = int(input())
An = list(map(int, sys.stdin.readline().rstrip().split()))

ans = 0
mn = 10**9
minus = 0
for a in An:
  mn = min(mn, abs(a))
  ans += abs(a)
  if a < 0:
    minus += 1

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

Solution (Python):
N = int(input())
count = 0
sumation = 0
min_num = 10 ** 9 + 1
for item in input().split():
  if int(item) < 0:
    count += 1
  sumation += abs(int(item))
  min_num = min(min_num, abs(int(item)))
if count % 2 == 0:
  print(sumation)
else:
  print(sumation - 2 * min_num)

Solution (Python):

import re
import bisect
from datetime import datetime as dt

n = input()
A = map(int, raw_input().split())
minus_count = 0
for a in A:
    if a < 0:
        minus_count += 1
ans = 0
for a in A:
    ans += abs(a)
if minus_count % 2 == 0:
    print ans
else:
    m = 10**10
    for a in A:
        if m > abs(a):
            m = abs(a)
    print ans - 2 * m

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

numbers_abs = [abs(n) for n in numbers]
sum_abs = sum(numbers_abs)
min_abs = min(numbers_abs)

count_negative = sum([1 for n in numbers if n < 0])

answer = sum_abs
if (count_negative % 2 == 1):
  answer = sum_abs - 2 * min_abs

print(answer)

Solution (Python):






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

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

print(ans)

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

num_of_minus = sum([a < 0 for a in A])
abs_A = [abs(a) for a in A]
ans = sum(abs_A)

if num_of_minus % 2 == 0:
    print(ans)
else:
    print(ans - 2 * min(abs_A))

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

for i in range(n):
    if a[i] < 0:
        b += 1
        a[i] = abs(a[i])
        
if (0 in a) or ((b % 2) == 0):
    pass
else:
    ans -= min(a) * 2

ans += sum(a)
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
total = 0
c = 0
small = 1000000000
for i in range(n):
    if a[i]<0:
        c+=1
        a[i] = abs(a[i])

    small= min(small,a[i])
if c&1:
    print(sum(a)-2*small)
else:
    print(sum(a))

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

if sum(x < 0 for x in A) % 2 == 0:
  result = sum(map(abs, A))
else:
  minimum_abs, idx = abs(A[0]), 0
  for i in range(1, N):
    if minimum_abs > abs(A[i]):
      minimum_abs, idx = abs(A[i]), i
  result = sum(map(abs, (v for i, v in enumerate(A) if i != idx))) - abs(minimum_abs)

print(result)

Solution (Python):
input()
a = list(map(int, input().split()))
nNegative = 0
total = 0
minVal = float('inf')
for num in a:
    if num < 0:
        num *= -1
        nNegative += 1
    minVal = min(minVal, num)
    total += num
print(total if nNegative & 1 == 0 else total - 2 * minVal)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
dp = [[0]*(2) for _ in range(n+1)]
dp[0][1] = -10**8
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[-1][0])

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

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

ans = 0
pc, zc, mc = 0, 0, 0
s = 0
min_abs = 10**9
for a in A:
    abs_a = abs(a)
    min_abs = min(min_abs, abs_a)
    s += abs_a
    if a>0:
        pc += 1
    elif a==0:
        zc += 1
    else:
        mc += 1

if zc>0 or mc%2==0:
    print(s)
else:
    print(s-2*min_abs)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve1():
    _ = int(input())
    L = list(map(int, input().split()))

    S = sum([abs(v) for v in L])
    if len(list(filter(lambda x: x < 0, L))) % 2 == 0:
        print(S)
    else:
        print(S-2*(min([abs(v) for v in L])))


def solve2():
    N = int(input())
    L = list(map(int, input().split()))
    dp = [[0]*(N+1) for _ in range(2)]
    dp[1][0] = -float('inf')
    for i in range(N):
        dp[0][i+1] = max(dp[0][i]+L[i], dp[1][i]-L[i])
        dp[1][i+1] = max(dp[0][i]-L[i], dp[1][i]+L[i])
    print(dp[0][-1])


solve2()

Solution (Python):
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    a = f()

    cntp = 0
    cntn = 0
    cnt0 = 0

    total = 0
    miabs = int(1e10)
    for i in range(n):
        total += abs(a[i])
        miabs = min(miabs, abs(a[i]))
        if a[i]>0:
            cntp += 1
        elif a[i] < 0:
            cntn += 1
        else:
            cnt0 += 1
    

    if cntn%2 == 0 or cnt0 > 0:
        print(total)
    else:
        print(total - 2*miabs)


solve()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N = int(input())
L = list(map(int, input().split()))

S = sum([abs(v) for v in L])
if len(list(filter(lambda x: x < 0, L))) % 2 == 0:
    print(S)
else:
    print(S-2*(min([abs(v) for v in L])))

Solution (Python):
from numpy import*;_,a=open(0);a=int64(a.split());b=abs(a);print(sum(b)-sum(a<0)%2*min(b)*2)

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

dp = [[-float('inf')] * 2 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][1] + a[i], dp[i][0] - a[i])

print(dp[n][0])

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

minus = sum(x < 0 for x in a_l)

if minus%2==0:
    print(sum(abs(x) for x in a_l))
else:
    print(sum(abs(x) for x in a_l)-2*min(abs(x) for x in a_l))

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

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

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



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

min = min(a)

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * 2 for i 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):
if __name__ == "__main__":
    n = int(input())
    a = map(int, input().split())
    a = list(a)
    zerop = any(map(lambda x: x == 0, a))
    evenp = sum(map(lambda x: 1 if x < 0 else 0, a)) % 2 == 0
    abss = list(map(abs, a))
    ans = 0
    if zerop or evenp:
        ans = sum(abss)
    else:
        m = min(abss)
        i = abss.index(m)
        for j, elm in enumerate(a):
            if j == i:
                ans += -abs(elm)
            else:
                ans += abs(elm)
    print(ans)

Solution (Python):
import sys
N = int(sys.stdin.readline().strip())
As = list(map(int, sys.stdin.readline().strip().split()))

ans = 0
num_negative = 0
min_num = float('inf')
for A in As:
    ans += abs(A)
    min_num = min(min_num, abs(A))
    if A < 0:
        num_negative += 1
if num_negative % 2 == 1:
    ans -= 2 * min_num
print(ans)

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

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
s = 0
p = 0
m = 1000000001
for i in A:
    s += abs(i)
    if i <=0:
        p += 1
    m = min(m, abs(i))
if p % 2 == 1:
    s = s - 2 * m
print(s)

Solution (Python):
int(input())
a=[int(i) for i in input().split()]
b=[abs(int(i)) for i in a]
c=[int(i) for i in a if i<0]
b.sort()
print(sum(b)-[0,b[0]*2][len(c)%2])

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
 
absA = []
for i in range(N):
    absA.append(abs(A[i]))

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

print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
 
absA = []
for i in range(N):
    absA.append(abs(A[i]))

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

print(ans)

Solution (Python):
N = int( input())
A = list( map( int, input().split()))
S = [ -A[i] for i in range(N) if A[i] <= 0]
T = list( map( abs, A))
ans = sum(T)

if len(S)%2 != 0:
    ans -= min(T)*2
print(ans)

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


A_minus = [a for a in A if a < 0]
A_abs = [abs(a) for a in A]

if len(A_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()))
count_plus=0
count_minus=0
sum_all = 0

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

if count_minus % 2 == 0:
    print(sum_all)
else:
    print(sum_all - (min(A)*2))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
new_a = []
sum = 0
minus_count = 0
zero_flag = 0

for i in range(n):
	new_a.append(abs(a[i]))

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

if zero_flag == 1:
	for i in range(n):
		sum += abs(a[i])
elif minus_count % 2 == 0:
	for i in range(n):
		sum += abs(a[i])
else:
	for i in range(n):
		sum += new_a[i]
	sum = sum - min(new_a) * 2

print(sum)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
new_a = []
sum = 0
minus_count = 0
zero_flag = 0
min_a = 0

for i in range(n):
	new_a.append(abs(a[i]))

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

if zero_flag == 1:
	for i in range(n):
		sum += abs(a[i])
elif minus_count % 2 == 0:
	for i in range(n):
		sum += abs(a[i])
else:
	for i in range(n):
		sum += new_a[i]
	sum = sum - min(new_a) * 2

print(sum)

Solution (Python):
from fractions import gcd
def get_result(L, N):
    L_abs = [abs(x) for x in L]
    A = sum(L_abs)
    B = min(L_abs)
    neg_count = 0
    for elem in L:
        if elem < 0:
            neg_count += 1
    if neg_count % 2 == 0:
        return A
    else:
        return (A-2*B)


N = int(input())
L = [int(s) for s in input().split(" ")]
result = get_result(L, N)
print(result )

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

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

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

sum = 0
min = 1000000000
flag = 1
for i in range(n):
  sum += abs(A[i])
  if min > abs(A[i]):
    min = abs(A[i])
  if A[i] < 0:
    flag *= -1
    
if flag == 1:
  print(sum)
else:
  print(sum - min * 2)

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

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

main()

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

negative_count = len(list(filter(lambda x: x < 0, As)))

if negative_count % 2 is 0:
    print(sum(list(map(lambda x: abs(x), As))))
else:
    abs_list = list(map(lambda x: abs(x), As))
    min = min(abs_list)
    abs_list.remove(min)
    print(sum(abs_list) - min)

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

abs_list = []
count = 0
for i in range(n):
   abs_list.append(abs(a[i]))
   if a[i] < 0:
       count += 1

if count%2 == 1:
    print(sum(abs_list) - min(abs_list)*2)
else:
    print (sum(abs_list))

Solution (Python):


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

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

Solution (Python):
N=int(input())
A=[i for i in map(int,input().split())]

dp_p={}
dp_m={}
dp_p[0]=0
dp_m[0]=-9999999999

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

print(dp_p[N])

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

ans = 0

count = 0
existZero = False
for i in range(N):
    if A[i] == 0:
        existZero = True
    elif A[i] < 0:
        count += 1

    A[i] = abs(A[i])

if existZero:
    ans = sum(A)
else:
    if count % 2 == 0:
        ans = sum(A)
    else:
        ans = sum(A) - 2 * min(A)

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
dp=[[0,-1e10] 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][1]+a[i],dp[i][0]-a[i])
print(dp[n][0])

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

abs_list = [abs(a) for a in A]
count = 0
ans = 0

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

if count % 2 == 0:
    for i in range(N):
        ans += abs_list[i]
else:
    for i in range(N):
        ans += abs_list[i]
    ans -= 2*min(abs_list)

print(ans)

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

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

if count % 2 == 0:
    for i in range(n):
        a[i] = abs(a[i])
    total = sum(a)
else:
    for i in range(n):
        a[i] = abs(a[i])
    total = sum(a) - min(a)*2

print(total)

Solution (Python):
from functools import reduce
N=int(input())
NS=[int(i) for i in input().split()]
Nminus = 0
Nzero = 0
minabs = 9223372036854775807
abssum = 0
for i in NS:
    if i < 0:
        Nminus += 1
    elif i == 0:
        Nzero += 1
    minabs = min(abs(i), minabs)
    abssum += abs(i)

if Nminus % 2 == 0 or Nzero > 0:
    print(abssum)
else:
    print(abssum - 2*minabs)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A = [0] + A
dp0 = [0]*(N+1)
dp1 = [0]*(N+1)
dp0[2] = A[1]+A[2]
dp1[2] = -A[1]-A[2]
for i in range(3,N+1):
  dp0[i] = max(dp0[i-1],dp1[i-1])+A[i]
  dp1[i] = max(dp0[i-1]-2*A[i-1],dp1[i-1]+2*A[i-1])-A[i]
print(max(dp0[N],dp1[N]))

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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
t = 0
for c in a: 
  if c < 0: t = 1 - t
if t:
  t = abs(a[0])
  s = 0
  for c in a:
    t = min(t, abs(c))
    s += abs(c)
  print(s - t - t)
else:
  s = 0
  for c in a:
    s += abs(c)
  print(s)

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


ans = 0
num_minus = 0
min_num = 1e+9
for i in range(N):
    ans += abs(A[i])
    min_num = min(min_num, abs(A[i]))
    if A[i] < 0: num_minus += 1

if num_minus%2 == 0: print(ans)
else: print(ans - 2*min_num)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
x,m,num = 10**9,0,0
for i in a:
    if i<0: m+=1
    x = min(abs(i),x)
    num+=abs(i)
if x and m%2: print(num-2*x)
else: print(num)

Solution (Python):


N = int(input())
A = [int(i) for i in input().split()]
abs_A = list(map(abs, A))

SUM = sum(abs_A)

minus = len(list(filter(lambda a: a < 0, A)))
if minus % 2 == 0:
    print(SUM)
else:
    m = min(abs_A)
    print(SUM - 2*m)

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

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

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

        print(sum(A) - dele)

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

Solution (Python):
def flipping_signs(N: int, A: list)->int:
    
    
    
    min_abs = float('inf')
    s = 0
    neg_n = 0
    for a in A:
        s += abs(a)
        if a < 0:
            neg_n += 1
        min_abs = min(abs(a), min_abs)

    
    if neg_n & 1:
        return s - 2*min_abs
    return s


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]

    ans = flipping_signs(N, A)
    print(ans)