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())
lis = list(map(int, input().split()))

if 0 in lis:
    ans = 0
    for i in lis:
        if i < 0:
            ans += -1 * i
        else:
            ans += i
    print(ans)
    exit()

minus = [0]*n
for i in range(n):
    if lis[i] < 0:
        minus[i] = 1

if sum(minus) % 2 == 0:
    ans = 0
    for i in lis:
        if i < 0:
            ans += -1 * i
        else:
            ans += i
    print(ans)
else:
    ans = 0
    m = 10**9+1
    for i in lis:
        if i < 0:
            ans += -1*i
        else:
            ans += i
        m = min(m, abs(i))
    print(ans - 2*m)

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

cnt_fu = 0
cnt_0 = 0
ans = 0
b = []
for i in range(n):
    ans += abs(a[i])
    b.append(abs(a[i]))
    if a[i]<0:
        cnt_fu += 1
    if a[i]==0:
        cnt_0 += 1

if cnt_fu%2==0:
    print(ans)
else:
    print(ans-min(b)*2)

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

ans = 0
neg = 0
zero = False
smallest = abs(a[0])

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

    if abs(a[i]) < smallest:
        smallest = abs(a[i])

    if a[i] == 0:
        zero = True
    elif a[i] < 0:
        neg += 1

if neg % 2 == 1 and not zero:
    print(ans-2*smallest)
else:
    print(ans)

Solution (Python):

import sys
import numpy as np
import math


n = int(input())
aList = list(map(int, input().split()))
numMinus = 0
for i in range(n):
	if aList[i] < 0:
		numMinus += 1
		aList[i] *= -1

aList.sort()

if numMinus % 2 == 0:
	print(sum(aList))
else:
	print(sum(aList) - 2 * aList[0])

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

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
abs_A = list(map(lambda x: abs(x), A))
abs_A = sorted(abs_A)
min_cnt = 0
ans = 0

for a in A:
    if a < 0:
        min_cnt += 1
    ans += abs(a)

if min_cnt % 2 == 1:
    ans -= 2 * abs_A[0]
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
dp=[[0,0]for _ in range(n)]
dp[0]=[a[0],-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):
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N = NI()
    A = NLI()
    
    cnt = 0
    minimum_abs = 10**9
    ans = 0
    flag = 0
    
    for n in range(N):
        ans += abs(A[n])
        minimum_abs = min(abs(A[n]),minimum_abs)
        if A[n] < 0:
            cnt += 1
        elif A[n] == 0:
          flag = 1

                
    if cnt % 2 == 0 or flag == 1:
        print(ans)
    else:
        print(ans - minimum_abs * 2)
            


if __name__ == '__main__':
    main()

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

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

Solution (Python):


INF = 10**9 + 1

def solve(n,a):
    ans = 0
    minusCount = 0
    minimumNum = INF
    lst = []
    for i in range(n):
        if a[i] < 0:
            minusCount += 1
        ans += abs(a[i])
        minimumNum = min(minimumNum,abs(a[i]))
    if minusCount % 2 == 0:
        pass
    else:
        ans -= minimumNum*2
    return ans


def main():
    N = int(input())
    a = list(map(int,input().split()))
    print(solve(N,a))

if __name__ == '__main__':
    main()

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

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

cnt=0
ans=0

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



if cnt%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()))

A_plus = []
A_zero = []
A_minus = []

a_abs_min = 10**10

for a in A:
    if a > 0:
        A_plus.append(a)
    elif a == 0:
        A_zero.append(a)
    else:
        A_minus.append(a)
        
    if abs(a) < a_abs_min:
        a_abs_min = abs(a)
        
if len(A_minus)%2 == 0:
    ans = sum(A_plus)-sum(A_minus)
else:
    ans = sum(A_plus)-sum(A_minus) - 2*a_abs_min
print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    neg = total = 0
    min_abs = INF
    for a in A:
        if a < 0:
            neg += 1
        total += abs(a)
        if min_abs > abs(a):
            min_abs = abs(a)

    if neg % 2 == 1:
        total -= 2 * min_abs

    print(total)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    neg = sum(1 for a in A if a < 0)
    ans = sum(abs(a) for a in A)

    if neg % 2 == 1:
        ans -= 2 * min(abs(a) for a in A)

    print(ans)
    return


if __name__ == '__main__':
    main()

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

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    neg = 0
    m = INF
    for i in range(N):
        if A[i] < 0:
            neg += 1
            A[i] = - A[i]
        m = min(m, A[i])

    if 0 in A:
        print(sum(A))
    else:
        print(sum(A) - (2 * m)*(neg % 2))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

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

if cnt % 2 == 0:
    B = [abs(a) for a in A]
    ans = sum(B)
else:
    C = [abs(a) for a in A]
    C_min = min(C)
    C_min_id = C.index(C_min)

    C[C_min_id] = C[C_min_id] * (-1)
    ans = sum(C)
print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
minus = 0
plus = 0
zero = 0
ans_A = []
for a in A:
    if a < 0:
        minus += 1
    elif a > 0:
        plus += 1
    else:
        zero += 1
    ans_A.append(abs(a))

ans_A.sort()

if zero > 0:
    print(sum(ans_A))
    exit()
if minus % 2 == 0:
    print(sum(ans_A))
else:
    print(sum(ans_A[1:])-ans_A[0])

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

Solution (Python):
from bisect import bisect_left,bisect,bisect_right
import sys

icase=0
if icase==0:
    n=int(input())
    a=list(map(int,input().split()))

a.sort()
ii=bisect(a,0)

if ii==n:
    if ii%2==0:
        asum=-sum(a)
    else:    
        asum=-sum(a[0:ii-1])+a[ii-1]
    print(asum)
    sys.exit()

if ii%2==0:
    asum=-sum(a[0:ii])+sum(a[ii:])
else:
    if -a[ii-1]<a[ii]:
        d=a[ii-1]+a[ii]
    else:
        d=-a[ii-1]-a[ii]
    asum=-sum(a[0:ii-1])+d+sum(a[ii+1:])

print(asum)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
count=0
ans=[]
for i in range(n):
  ans.append(abs(a[i]))
  if a[i]<0:
    count+=1

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

Solution (Python):
import numpy
N = int(input())
a = numpy.array([int(i) for i in input().split()])
min =  10**9+1
minus = 0
total = 0
for i in a :
    if i < 0 :
        minus += 1
    if abs(i) < min :
        min = abs(i)
    total += abs(i)

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

Solution (Python):
N = int(input())
cnt = 0
m = float("inf")
S = 0
for a in map(int, input().split()):
    m = min(m, abs(a))
    if a < 0:
        cnt += 1
        S -= a
    else:
        S += a
if cnt%2:
    print(S-2*m)
else:
    print(S)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

if cnt % 2:
    m = inf
    ans = 0
    for i in range(n):
        m = min(m, abs(a[i]))
        ans += abs(a[i])
    ans -= 2*m
    print(ans)
else:
    ans = 0
    for i in range(n):
        ans += abs(a[i])
    print(ans)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_table(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N = I()
    A = LI()
    cnt = sum([1 for ai in A if ai < 0])
    B = [abs(ai) for ai in A]
    if cnt % 2 == 0:
        print(sum(B))
    else:
        print(sum(B) - min(B) * 2)


if __name__ == '__main__':
    main()

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    
    dp = [[float('inf')] * N for _ in range(2)]
    dp[0][0] = A[0]
    dp[1][0] = -A[0]
    for i, a in enumerate(A[1:], 1):
        dp[0][i] = max(dp[0][i-1]+a, dp[1][i-1]-a)
        dp[1][i] = max(dp[0][i-1]-a, dp[1][i-1]+a)
    return max(dp[0][N-2]+A[-1], dp[1][N-2]-A[-1])



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)]  
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
tmp = 10**10
minus = 0
zeros = 0
ans = 0
for a in A:
  if a > 0:
    ans += a
    tmp = min(tmp, a)
  elif a == 0:
    zeros += 1
  else:
    a = -a
    ans += a
    minus += 1
    tmp = min(tmp, a)
if minus % 2 == 1 and zeros == 0:
  ans -= tmp*2
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
import bisect
A.sort()
B=[abs(i) for i in A]
l=min(B)
count=0
for i in range(N):
  if A[i]<0:
    count+=1
  else:
    break
if count%2==1:
  for i in range(count-1):
    A[i]=-A[i]

  print(sum(A)-2*l-2*A[count-1])

if count%2==0:
  for i in range(count):
    A[i]=-A[i]
  print(sum(A))

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

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

s = 0

b = [abs(x) for x in a]

c = 0
for x in a:
    if x < 0:
        c += 1

if c % 2 == 0:
    s = sum(b)
else:
    s = sum(b) - 2 * min(b)

print(s)

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

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

if (minus%2==0)|(zero==1):
    print(sum(A))
else:
    print(sum(A)-2*min(A))

Solution (Python):


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

INF = float('inf')
abs_min = INF
neg_cnt = 0
res = 0

for i in range(N):
    if A[i] < 0:
        neg_cnt += 1
    abs_min = min(abs_min, abs(A[i]))
    res += abs(A[i])

if neg_cnt % 2:
    res -= 2 * abs_min

print(res)

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

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

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

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

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

Solution (Python):

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

dp = [[0, 0] for _ in range(N + 1)]
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[-1][0])

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

num_odd_minus = 0
res = 0
min_num = abs(a[0])
for num in a:
    if num < 0:
        num_odd_minus += 1
    abs_num = abs(num)
    res += abs_num
    if min_num > abs_num:
        min_num = abs_num

if num_odd_minus % 2 == 1:
    res -= min_num * 2

print(res)

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


if __name__ == '__main__':
    main()

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

if 0 in A:
    S=0
    for a in A:
        S+=abs(a)
    print(S)
else:
    X=0
    S=0
    for a in A:
        X+=(a<0)
        S+=abs(a)

    if X%2==0:
        print(S)
    else:
        b=abs(min(A,key=lambda x:abs(x)))
        print(S-2*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
if count%2==0:
    for j in range(n):
        a[j]=abs(a[j])
    print(sum(a))
else:
    for j in range(n):
        a[j]=abs(a[j])
    print(sum(a)-2*min(a))

Solution (Python):

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

y = [abs(v) for v in X]
if sum(v < 0 for v in X) % 2 == 0:
    print(sum(y))
else:
    print(sum(y) - 2 * min(y))

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

if __name__ == "__main__":
    main()

Solution (Python):



import numpy as np

n = int(input())

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

minus_signs = sum([1 for _ in a if np.sign(_) == -1])

if minus_signs % 2 == 0:
    res = sum([abs(_) for _ in a])
else:
    _min = min([abs(_) for _ in a])
    res = sum([abs(_) for _ in a])

    res = res - _min - _min

print(res)

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

dp = [[0]*2 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):
n = int(input())
A = list(map(int,input().split()))

minus = 0
zero = 0

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

A2 = [abs(i) for i in A]
if minus %2 == 0 or zero >= 1:
    print(sum(A2))
else:
    print(sum(A2)-2*min(A2))

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


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

_min = 10**9 + 1
flag = False  
_sum = 0

for a in A:
    _sum += abs(a)
    _min = min(_min, abs(a))
    if a < 0:
        flag = not flag

if flag:
    _sum -= _min * 2
print(_sum)

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

min_abs = 10**9
abs_sum = 0
minus_cnt = 0
zero_cnt = 0
for a in al:
    if a < 0: minus_cnt+=1
    elif a == 0: zero_cnt+=1
    abs_sum += abs(a)
    min_abs = min(min_abs, abs(a))

if minus_cnt%2 == 0:
    print(abs_sum)
else:
    if zero_cnt > 0:
        print(abs_sum)
    else:
        print(abs_sum-min_abs*2)

Solution (Python):
import math
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import product
from collections import defaultdict
from collections import deque
from collections import Counter
import heapq


def input_li():
    return list(map(int, input().split()))


def input_int():
    return int(input())


N = input_int()
A_LI = input_li()
dp = [[0] * 2 for _ in range(N)]
dp[0][0] = A_LI[0]
dp[0][1] = -A_LI[0]
for i in range(1, N):
    dp[i][0] = max(dp[i - 1][0] + A_LI[i], dp[i - 1][1] - A_LI[i])
    dp[i][1] = max(dp[i - 1][0] - A_LI[i], dp[i - 1][1] + A_LI[i])
print(dp[-1][0])

Solution (Python):
import math
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import product
from collections import defaultdict
from collections import deque
from collections import Counter
import heapq


def input_li():
    return list(map(int, input().split()))


def input_int():
    return int(input())


N = input_int()
A_LI = input_li()
minus_cnt = 0
for a in A_LI:
    if a < 0:
        minus_cnt += 1

ans = 0
abs_min = 10 ** 9
for a in A_LI:
    ans += abs(a)
    abs_min = min(abs_min, abs(a))
print(ans) if minus_cnt % 2 == 0 else print(ans - abs_min * 2)

Solution (Python):

n, *a = map(int, open(0).read().split())
for i in range(n - 1):
    if a[i] < 0:
        a[i] *= -1
        a[i + 1] *= -1
print(sum(a) - 2 * min(abs(i) for i in a) - 2 * a[-1] if a[-1] < 0 else sum(a))

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

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

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

dp[-1][0] = dp[-2][0]-As[-1]
dp[-1][1] = dp[-2][1]+As[-1]

print(max(dp[-1]))

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

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
m = 0
z = 0
for i in range(N):
    if A[i]<0:
        m += 1
    elif A[i]==0:
        z += 1
m = m%2
B = sorted([abs(A[i]) for i in range(N)])
p = m-z
if p>0:
    for i in range(z,z+p):
        B[i] = -B[i]
    print(sum(B))
else:
    print(sum(B))

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

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

plus = []

minas = []

for value in a:
    if value < 0:
        minas.append(abs(value))
    else:
        plus.append(value)

if len(minas)%2 == 0:
    ans = sum(plus)+sum(minas)
else:
    if len(plus) > 0:
        mini = min(min(plus),min(minas))
        ans = sum(plus)+sum(minas)-mini*2
    else:
        mini = min(minas)
        ans = sum(minas)-mini*2

print(ans)

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

cnt = len([a for a in A if a < 0])
if cnt % 2 == 0:
    print(sum([abs(a) for a in A]))
else:
    ans = sum([abs(a) for a in A])
    M = float('inf')
    for a in A:
        if abs(a) < M:
            M = abs(a)
    print(ans - 2 * M)

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

INF = float('inf')
dp = [[-INF]*2 for _ in range(N+1)]
dp[0][0] = 0
for i,a in enumerate(A):
    dp[i+1][0] = max(dp[i+1][0], dp[i][0]+a, dp[i][1]-a)
    dp[i+1][1] = max(dp[i+1][1], dp[i][0]-a, dp[i][1]+a)
print(dp[-1][0])

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

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

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

if cnt%2==0:
    print(sum(abs(Ai) for Ai in A))
else:
    A.sort(key=lambda x: abs(x))
    print(-abs(A[0])+sum(abs(Ai) for Ai in A[1:]))

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)







INF = 1 << 50



def run():
    N, *A = map(int, read().split())

    SUM = sum([abs(a) for a in A])
    if A.count(0):
        print(SUM)
        return

    do = [0]
    for a in A[:-1]:
        if not do[-1]:
            if a > 0:
                do.append(0)
            else:
                do.append(1)
        else:
            if a > 0:
                do.append(1)
            else:
                do.append(0)

    if A[-1] > 0:
        if do[-1]:
            base_ans = SUM - abs(A[-1]) * 2
        else:
            print(SUM)
            return
    else:
        if do[-1]:
            print(SUM)
            return
        else:
            base_ans = SUM - abs(A[-1]) * 2
    ans = base_ans
    for i in range(N-1):
        ans = max(ans, base_ans - abs(A[i]) * 2 + abs(A[-1]) * 2)

    print(ans)





if __name__ == "__main__":
    run()

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

Solution (Python):






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





a_abs = list(map(abs,A))
minus_cnt = sum([1 for x in A if x < 0])
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()))
cnt = sum([1 for i in a if i < 0])
if cnt%2:
  r = 10**9
  for i in range(n):
    r = min(r,abs(a[i]))
  print(sum([abs(x) for x in a])-2*r)  
else:
  print(sum([abs(x) for x in a]))

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

ans, count = 0, 0
for i in range(n):
    ans += abs(a[i])
    if a[i] < 0:
        count += 1
a = list(abs(i) for i in a)
if count%2 != 0:
    ans -= 2*min(a)
print(ans)

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

b = list(map(abs, a))
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()))

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

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

Solution (Python):


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

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

dp[1][False] = N_List[0] + N_List[1]
dp[1][True] = (N_List[0] + N_List[1])*(-1)

for i in range(2,N):
    dp[i][False] = max(dp[i-1][True] + N_List[i],dp[i-1][False] + N_List[i])
    dp[i][True] = max(dp[i-1][True] + N_List[i-1]*2 + N_List[i]*(-1) ,
                      dp[i-1][False] + N_List[i-1]*(-2) + N_List[i]*(-1))

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

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

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

for i in range(n):
  if a[i]<0:
    check=check+1
a=list(map(lambda x:abs(x),a))

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

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**18

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

Solution (Python):
n = int(input())
a_list = [int(x) for x in input().split()]
count = 0
ans = 0
m = 10 ** 9
for i in range(n):
    if a_list[i] < 0:
        a_list[i] *= -1
        count += 1
    ans += a_list[i]
    if a_list[i] < m:
        m = a_list[i]
if count % 2 == 1:
    ans -= m * 2
print(ans)

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] = -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()))
import bisect
a.sort()

idx = bisect.bisect_left(a, 0)
sm = [abs(x) for x in a]
if idx % 2 == 0:
    print(sum(sm))
else:
    print(sum(sm) - 2*min(sm))

Solution (Python):
import sys

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


ans = 0
for a in A:
    ans += abs(a)

c = 0
m = abs(A[0])
for a in A:
    if a < 0:
        c += 1
    elif a == 0:
        print(ans)
        sys.exit()

    if abs(a) < m:
        m = abs(a)

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

Solution (Python):
import sys

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


ans = 0
for a in A:
    ans += abs(a)

c = 0
m = abs(A[0])
for a in A:
    if a < 0:
        c += 1
    elif a == 0:
        print(ans)
        sys.exit()

    if abs(a) < m:
        m = abs(a)

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

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

A_tmp = sorted(A, key=abs, reverse=True,)
total = 0
for i,v in enumerate(A_tmp):
    if (v <= 0) and (i < len(A_tmp)-1):
        v *= (-1)
        A_tmp[i+1] = (-1) * A_tmp[i+1]
    total += v
print(total)

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

A_tmp = sorted(A, key=abs, reverse=True,)
total = 0
for i,v in enumerate(A_tmp):
    if (v <= 0) and (i < len(A_tmp)-1):
        A_tmp[i] = (-1) * A_tmp[i]
        A_tmp[i+1] = (-1) * A_tmp[i+1]
        total += A_tmp[i]
    else:
        total += v
print(total)