Problem:


Score : 400 points

Problem Statement

There are N integers, A_1, A_2, ..., A_N, arranged in a row in this order.

You can perform the following operation on this integer sequence any number of times:

Operation: Choose an integer i satisfying 1 \leq i \leq N-1. Multiply both A_i and A_{i+1} by -1.

Let B_1, B_2, ..., B_N be the integer sequence after your operations.

Find the maximum possible value of B_1 + B_2 + ... + B_N.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

-10^9 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible value of B_1 + B_2 + ... + B_N.

Sample Input 1

3
-10 5 -4

Sample Output 1

19

If we perform the operation as follows:

Choose 1 as i, which changes the sequence to 10, -5, -4.

Choose 2 as i, which changes the sequence to 10, 5, 4.

we have B_1 = 10, B_2 = 5, B_3 = 4. The sum here, B_1 + B_2 + B_3 = 10 + 5 + 4 = 19, is the maximum possible result.

Sample Input 2

5
10 -4 -8 -11 3

Sample Output 2

30

Sample Input 3

11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000

Sample Output 3

10000000000

The output may not fit into a 32-bit integer type.



Sample input:
3
-10 5 -4


Sample output:
19

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = LIST()
dp = [[0]*n for i in range(2)]
# dp[0][i]: {a[i], a[i+1]}に-1を乗算しないときのa[i]までの和の最大値
# dp[1][i]: {a[i], a[i+1]}に-1を乗算したときのa[i]までの和の最大値

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

print(dp[0][-1])

Submission status: Accepted

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

cnt = sum(i < 0 for i in a)
ans = sum(abs(i) for i in a)
if cnt % 2 == 0:
    print(ans)
elif cnt % 2 == 1:
    print(ans - 2 * min(abs(i) for i in a))

Submission status: Accepted

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

ans = 0
c = 0
tmp_m = 10**9
zero = False
for i in range(n):
    if a[i] < 0:
        c += 1
    elif a[i] == 0:
        zero = True
    tmp = abs(a[i])
    ans += tmp
    tmp_m = min(tmp_m,tmp)

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

Submission status: Accepted

Solution code:
import sys

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

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007
    
    N = ii()
    A = lmi()

    mz_count = 0 # minus or zero
    mz_min = 10 ** 10
    ans = 0
    for i in A:
        if i <= 0:
            mz_count += 1
            i = -i
        ans += i
        if mz_min > i:
            mz_min = i
    
    if mz_count % 2 == 0:
        print(ans)
    else:
        print(ans - 2 * mz_min)    

    return

main()

Submission status: Accepted

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

# 絶対値の和
plus_sum = 0
# 負の数の個数
minus_num = 0
# 絶対値が最も小さい数
min_abs = 10**10

for a in A:
    plus_sum += abs(a)
    if a < 0:
        minus_num += 1
    if abs(a) < abs(min_abs):
        min_abs = a

# 0が入っていたら全部正にできる
if 0 in A:
    print(plus_sum)

else:
    # 0が含まれない場合、負の個数の偶奇で場合分け
    # 偶数個なら全部正にできる
    if minus_num % 2 == 0:
        print(plus_sum)

    # min_absだけマイナス、他はプラス
    elif minus_num % 2 == 1:
        ans = plus_sum - 2 * abs(min_abs)
        print(ans)

Submission status: Accepted

Solution code:
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)

if (len(minus) % 2 == 0 or 0 in plus):
    # 全てを正にできる
    print(sum(plus) - sum(minus))
    exit()

# 絶対値がもっとも小さいものを探す
min_abs = 10**9 + 7
for i in A:
    min_abs = min(min_abs, abs(i))

sum_ans = 0
for i in A:
    sum_ans += abs(i)

print(sum_ans - min_abs * 2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
lst = list(map(int, input().split()))
mcnt = 0
for i in range(n):
  if lst[i] < 0:
    mcnt += 1
if 0 in lst or mcnt % 2 == 0:
  print(sum(list(map(abs, lst))))
  exit()
m = min(lst, key=abs)
print(sum(list(map(abs, lst))) - 2 * abs(m))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a_abs = [0]*n
is_minus = [0]*n

for i in range(n):
    if a[i] >= 0:
        a_abs[i] = a[i]
    else:
        a_abs[i] = -1 * a[i]
        is_minus[i] = 1

a_abs.sort()
if sum(is_minus) % 2 == 0:
    ans = sum(a_abs)
else:
    ans = sum(a_abs) - 2*a_abs[0]

print(ans)

Submission status: Accepted

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

mi=10**9+1
S=0
cnt=0
for i in range(N):
    if A[i]<0:
        cnt+=1
    a=abs(A[i])
    S+=a
    mi=min(mi,a)

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

Submission status: Accepted

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

pos = []
neg = []
ans = 0

for e in A:
    if e > 0:
        pos.append(e)
    else:
        neg.append(e)
if len(neg) % 2 == 0:
    ans = sum(abs_A)
else:
    """pos.sort(reverse=True)
    neg.sort(reverse=True)
    if len(neg) == N:
        ans = -sum(neg[:-1]) + neg[-1]
    else:"""
    #ans = max(-sum(neg[:-1]) + neg[-1], -sum(neg[:-3]) + sum(neg[-3:]))
    #ans = max(sum(pos[:-1])-pos[-1]-sum(neg), sum(pos) + neg[0] -sum(neg[1:]))
    ans = sum(abs_A)
    ans -= 2 * min(abs_A)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
tmp=float("inf")
flg=True
b=list(map(lambda x:abs(x),a))
ans=sum(b)
t=sum(b)
for i in range(n):
    if a[i]==0:
        print(ans)
        exit()
    if a[i]<0:
        if flg:
            flg=False
        else:
            flg=True
    if abs(a[i])<tmp:
        tmp=abs(a[i])
if flg:
    print(ans)
else:
    print(ans-2*tmp)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

sum = 0
for i in a:
    sum += abs(i)

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

Submission status: Accepted

Solution code:
n = int(input())
alst = list(map(int, input().split()))
minus = 0
for num in alst:
    if num < 0:
        minus += 1

blst = [abs(num) for num in alst]
blst.sort()

if 0 in alst:
    print(sum(blst))
elif minus % 2 == 0:
    print(sum(blst))
else:
    print(sum(blst[1:]) - blst[0])

Submission status: Accepted

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

cnt = 0
l = []
for a in A:
  if a < 0:
    cnt += 1
  l.append(abs(a))

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

Submission status: Accepted

Solution code:
N = int(input())

Alist = list(map(int, input().split()))
plus = [abs(a) for a in Alist]

cnt = 0

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

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

Submission status: Accepted

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

Submission status: Accepted

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

import numpy as np

neg_cnt = len(list(filter(lambda x: x<0, A)))
abs_lis = np.abs(A)
sum_abs = sum(abs_lis)
if neg_cnt % 2 ==0:
    print(sum_abs)
else:
    print(sum_abs-2*min(abs_lis))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[0]*3 for _ in range(n+1)]
dp[0][0]=0
dp[0][1]=-10**10#i文字目,0反転してない,1反転してる

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
sm=sum(map(abs,a))
f=1

for i in range(n-1):
  f= 1 if a[i]*f>=0 else -1
print (sm if f*a[n-1]>0  or 0 in a else sm-2*min(map(abs,a)))

Submission status: Accepted

Solution code:
import sys
n=int(input())
A=list(map(int,input().split()))
count=0
for elem in A:
    if elem < 0:
        count+=1
if count%2==0:
    for i in range(len(A)):
        A[i]=abs(A[i])
    print(sum(A))
    sys.exit()
else:
    tmp=1000000000000
    for elem in A:
        tmp=(min(tmp,abs(elem)))
    for i in range(len(A)):
        A[i]=abs(A[i])
    print(sum(A)-2*tmp)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()
a = [abs(x) for x in A] #Aの絶対値

n = sum([A[i] != a[i] for i in range(N)]) #Aの中で負のものは何個あるか

if n%2:
	print(sum(a) - 2*min(a))
else:
	print(sum(a))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()

cnt = 0
for i, x in enumerate(A):
	if x < 0:
		cnt += 1
		A[i] *= -1

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

Submission status: Accepted

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

minus = 0
for i in range(N):
    minus += A[i] < 0

if minus % 2 == 0:
    print(sum(abs_A))
else:
    mini = float('inf')
    for i in range(N):
        mini = min(mini, abs_A[i])
    print(sum(abs_A) - 2*mini)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A_abs = []
cnt = 0
ans = 0

for a in A:
    if a < 0:
        cnt += 1
    A_abs.append(abs(a))

if A_abs.count(0) > 0:
    print(sum(A_abs))
elif cnt % 2 == 0:
    print(sum(A_abs))
else:
    print(sum(A_abs)- 2 * min(A_abs))

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())
minus_cnt = len([1 for A in a if A < 0])
ans = sum([abs(A) for A in a])
if (0 not in a) and (minus_cnt %2 != 0):
    ans -= 2 * min([abs(A) for A in a])
print(ans)

Submission status: Accepted

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

def main(n,a):
    sump=0
    summ=0
    minm=-10**9
    minp=10**9
    countm=0
    for i in range(n):
        if a[i]>=0:
            sump+=a[i]
            minp=min(minp,a[i])
        else:
            countm+=1
            summ+=a[i]
            minm=max(minm,a[i])
    #print(sump,summ,countm,minm,minp)
    if countm%2==0:
        return sump-summ
    else:
        return sump-summ-min(minp,abs(minm))*2

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(ans)

Submission status: Accepted

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

m = 0
ans = []
for i in a:
  if i < 0:
    m += 1
    ans.append(abs(i))
  else:
    ans.append(i)
if m % 2 == 0:
  print(sum(ans))
else:
  x = min(ans)
  print(sum(ans)-x*2)

Submission status: Accepted

Solution code:
n = int(input())
plus = []
minus = []
for a in map(int,input().split()):
    if a>=0:
        plus.append(a)
    else:
        minus.append(a)
ans = sum(plus)-sum(minus)
if len(minus)%2==1:
    if plus==[]:
        ans = ans + 2*max(minus)
    else:
        ans = ans - 2*min(abs(max(minus)),min(plus))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

cnt = 0

for v in a:
    if v < 0:
        cnt += 1
a = [abs(x) for x in a]

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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 ** 9 + 7

# map(int, input().split())
# list(map(int, input().split()))

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

negs = 0
abs_min = INF
total = 0
for a in A:
    if a < 0:
        negs += 1
    abs_min = min(abs_min, abs(a))
    total += abs(a)

if negs % 2 == 0:
    print(total)
else:
    print(total - abs_min * 2)

Submission status: Accepted

Solution code:
import collections
N =int(input())
As = [int(item) for item in input().split()]

cnt = 0
Bs = collections.deque()
min1 = 1000000000000

for i in As:
	if i < 0:
		cnt +=1
	Bs.append(abs(i))
	min1=min(min1, abs(i))
	
if cnt % 2 ==0:
	print(sum(list(Bs)))
else:
	print(sum(list(Bs))-min1*2)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
cnt = 0
cnt_0 = 0
for i in range(n):
    if a[i] < 0:
        cnt += 1
    elif a[i] == 0:
        cnt_0 += 1
    b[i] = abs(a[i])

if cnt % 2 == 0 or cnt_0 >= 1:
    ans = sum(b)
else:
    ans = sum(b) - min(b) * 2

print(ans)

Submission status: Accepted

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

dp=[[0]*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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# DPで解く方法
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n = I()
a = LI()
# dp[i][j] : i を選んで ai と ai + 1 の符号を反転(j = 0 させない, j = 1 させる)場合の a1 + a2 + ... + ai-1 + ai の最大値
dp = [[0] * 2 for _ in range(n + 1)]
dp[0][0] = 0  # dp[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])  # i + 1を選んで反転させない
    dp[i + 1][1] = max(dp[i][0] - a[i], dp[i][1] + a[i])  # i + 1を選んで反転させる
print(dp[n][0])

Submission status: Accepted

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n = I()
a = LI()
# i を選んで ai と ai+1の符号を入れ替える は
# x, y (x < y) を選んでax と ay の符号を入れ替える ことと同値(y - x 回 上の操作を行えばそうなる事がわかる)
cnt = [0, 0, 0]  # 正, 負, 0 の個数
for i in a:
    if i < 0:
        cnt[1] += 1
    elif i > 0:
        cnt[0] += 1
    else:
        cnt[2] += 1
if cnt[1] % 2 == 0 or cnt[2] > 0:
    ans = 0
    for i in a:
        ans += abs(i)
else:
    # 絶対値が最小の要素だけ負にする
    ans = 0
    for i in a:
        ans += abs(i)
    ans += -2 * min(abs(i) for i in a)
print(ans)

Submission status: Accepted

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

ans = 0
min_a = 10**9+1
flg = False
for i in range(n):
    ans += abs(a[i])
    if a[i] <= 0:
        flg = not flg
    min_a = min(min_a, abs(a[i]))

if flg:
    ans -= 2*min_a

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

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 make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#create date: 2020-06-29 15:39

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    a = na()
    a_abs = list()
    zero = False
    minus = 0
    for ai in a:
        if ai < 0:
            minus += 1
        elif ai == 0:
            zero = True
        a_abs.append(abs(ai))
    
    if minus % 2 == 0 or zero:
        print(sum(a_abs))
    else:
        print(sum(a_abs) - 2 * min(a_abs))
        

if __name__ == "__main__":
    main()

Submission status: Accepted

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

if 0 in A:
    ans = 0
    for i in range(N):
        ans += max(A[i], -A[i])
    print(ans)
    exit()
    
minus_count = 0
for i in range(N):
    if A[i] < 0:
        minus_count += 1
        
if minus_count % 2 == 0:
    ans = 0
    for i in range(N):
        ans += max(A[i], -A[i])
    print(ans)
else:
    for i in range(N):
        if A[i] < 0:
            A[i] = -A[i]
    min_A = min(A)
    print(sum(A) - 2*min_A)

Submission status: Accepted

Solution code:
N = int(input())

array = [int(i) for i in input().split()]
calc_array = []

cnt = 0

for n in array:
    if n < 0:
        cnt += 1
    calc_array.append(abs(n))
        
if cnt % 2 == 0 or 0 in calc_array:
    output = sum(calc_array)
else :
    output = sum(calc_array) - (2*min(calc_array))
    
print(output)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
A = list(map(int, input().split()))
INF = 10**9

dp = [[0]*2 for _ in range(n+1)] # dp[i][0]がiを選んで反転させない場合の最大値, dp[i][1]がiを選んで反転させた場合の最大値

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

for i in range(1,n+1):
    dp[i][0] = max(dp[i-1][0]+A[i-1], dp[i-1][1]-A[i-1]) # iを選んで反転させない時、 i-1を選んで反転させていなかったらiはそのままで、i-1を反転させていたらiは反転する
    dp[i][1] = max(dp[i-1][0]-A[i-1], dp[i-1][1]+A[i-1]) # iを選んで反転させる時、i-1を選んで反転させていなかったらiは反転していて、i-1を反転させていたらiはそのまま

print(dp[n][0]) # nを選ぶことはできない（n+1が存在しない）ため、答えはdp[n][0]

Submission status: Accepted

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

DP = [[0, 0] for _ in range(n + 1)]
DP[0][1] = -1e20
# print(DP)
for i in range(n):
    for j in [0, 1]:
        DP[i + 1][0] = max(DP[i][0] + A[i], DP[i][1] - A[i])
        DP[i + 1][1] = max(DP[i][0] - A[i], DP[i][1] + A[i])

print(DP[-1][0])

Submission status: Accepted

Solution code:
import numpy as np

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

cnt = np.sum(np.where(np.array(A) < 0, True, False))

#print(cnt)

A = list(map(lambda x:abs(x), A))


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

flip_a = [0]*n
cnt_minus = 0

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

flip_a.sort()

if cnt_minus%2 == 1:
	flip_a[0] = -flip_a[0]

print(sum(flip_a))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
mins=10**10
ct=0
for i in A:
 ans+=abs(i)
 mins=min(mins,abs(i))
 if i<0:
  ct+=1
if ct%2==1:
 ans-=2*mins
print(ans)

Submission status: Accepted

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

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

b.sort()
if c%2 == 1:
	b[0] = -b[0]
print(sum(b))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
INF = 10**9

dp0 = [0]
dp1 = [-INF-1]

for i, x in enumerate(A):
  dp0.append( max(dp0[i] + x, dp1[i] - x) )
  dp1.append( max(dp0[i] - x, dp1[i] + x) )

print(dp0[-1])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
INF = 10**9

dp0 = [0]
dp1 = [-INF-1]

for i, x in enumerate(A):
  dp0.append( max(dp0[i] + x, dp1[i] - x) )
  dp1.append( max(dp0[i] - x, dp1[i] + x) )

print(dp0[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*n
a=map(int,input().split())
    
z=0
result=0
min=1000000002

for i in a:
    if i<0:
        z+=1
    result+=abs(i)
    if abs(i)<min:
        min=abs(i)

if z%2==1:
    result-=min*2

print(result)

Submission status: Accepted

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

total_minus_num = 0
B = []
for a in A:
    if a < 0:
        total_minus_num += 1
    B.append(abs(a))

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

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    DP = [[-10 ** 20, -10 ** 20] for _ in range(N)] #[-1が偶数, -1が奇数]
    DP[0] = [A[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])
    #print(DP)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

A = list(map(int, input().split()))
A = np.array(A)
A_abs = np.abs(A)
M = np.sum(A_abs)
m = np.min(A_abs)

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

Submission status: Accepted

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

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

tmp = 0
zero = False
B = []
for a in A:
    if a < 0:
        tmp += 1
    elif a == 0:
        zero = True
    B.append(abs(a))

if tmp % 2 == 0 or zero:
    ans = sum(B)
else:
    ans = sum(B) - 2*min(B)

print(ans)

Submission status: Accepted

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

minus=[]
abses=[]
cnt=0
for i in range(n):
    if a[i]<0:
        minus.append(1)
    elif a[i]>0:
        minus.append(0)
    else:
        minus.append(0)
        cnt+=1
    abses.append(abs(a[i]))

if sum(minus)%2==0:
    print(sum(abses))
else:
    if cnt>0:
        print(sum(abses))
    else:
        print(sum(abses)- 2*min(abses))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
c = 0
k = 0
for i in range(N):
    if A[i] < 0:
        c += 1
        A[i] *= -1
    elif A[i] == 0:
        k = 1

if c % 2 == 0:
    print(sum(A))
elif k == 1:
    print(sum(A))
else:
    print(sum(A)-2*min(A))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
a = 0
for i in range(N):
  if A[i] < 0:
    a += 1
    A[i] *= -1
ans = sum(A)
if a % 2 == 1:
  A.sort()
  ans -= 2 * A[0]
print(ans)

Submission status: Accepted

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

num_minus = [a < 0 for a in A].count(True)

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

if num_minus%2 == 0:
    print(sum(B))
else:
    b = sorted(B)[0]
    print(sum(B) - 2*b)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
isMinus = False
for i in range(N):
    if A[i] < 0:
        isMinus = not isMinus
        A[i] = A[i]*-1

if isMinus:
    print(sum(A)-min(A)*2)
else:
    print(sum(A))

Submission status: Accepted

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

from functools import reduce

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N = II()
    A = LII()
  
    mn = 10 ** 9
    n = 0
    ans = 0
    for a in A:
        ans += abs(a)
        mn = min(mn, abs(a))
        if a < 0:
            n += 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))
def fde(): print("-flag-")

def main():
    N=ii()
    A=list(mi())
    
    dp = [[0]*2 for _ in range(10**5+10)]
    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[N-2]))



if __name__ == "__main__":
    main()

Submission status: Accepted

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

Flag = False
cnt = 0
S = 0
m = 10**9

for i in A:
  if i == 0:
    Flag = True
  elif i > 0:
    S += i
    m = min(m, i)
  else:
    S += -i
    cnt ^= 1
    m = min(m, -i)

if Flag or cnt == 0:
  print(S)
else:
  print(S-2*m)

Submission status: Accepted

Solution code:
N = int(input())
A_list = [int(e) for e in input().split()]

#全通りは 2**(N-1)なのでTLEする

#操作を考えると、-に対しては移動or打ち消しとなる。
#繰り返していくと-はどんどん打ち消される。
#最終的には
# - が奇数個 : 1個だけ残る。absをsumしたものから、abs最小分を引けばよい
# - が偶数個 : 全てが打ち消される。 ∴absをsumればOK

min_abs_A = 7 + 10**9
cnt_minus_in_A = 0
sum_abs_A = 0

for A in A_list:
    if A < 0:
        cnt_minus_in_A += 1
        
    if abs(A) < min_abs_A:
        min_abs_A = abs(A)
    
    sum_abs_A += abs(A)
    
if cnt_minus_in_A % 2 == 0:
    print(sum_abs_A)
else:
    print(sum_abs_A - 2*min_abs_A)

Submission status: Accepted

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

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

a.sort()

if cnt % 2 != 0:
    a[0] *= -1

print(sum(a))

Submission status: Accepted

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

A_plus = []
A_minus = []

for a in A:
    if a >= 0:
        A_plus.append(a)
    else:
        A_minus.append(a)

A_plus = sorted(A_plus)
A_minus = sorted(A_minus)


if len(A_minus) % 2 == 0:
    res = sum(A_plus) - sum(A_minus)
else:
    if len(A_plus) > 0:
        res = sum(A_plus) - sum(A_minus) - 2*min(A_plus[0], (-1)*A_minus[-1])
    else:
        res = sum(A_plus) - sum(A_minus) + 2*A_minus[-1]

print(res)

Submission status: Accepted

Solution code:
import numpy as np

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

min_A = min(abs_A)

if (A < 0).sum() % 2:
    print(sum(abs_A) - min_A * 2)
else:
    print(sum(abs_A))

Submission status: Accepted

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

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

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

if zero_count==1 or minus_count%2==0:
    ans=sum(a)
else:
    heapq.heapify(a)
    mn=heapq.heappop(a)
    ans=sum(a)-mn

print(ans)

Submission status: Accepted

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

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

ans = 0
for i in range(0,N,1):
    ans += abs(A[i])

minabs = 10**10
if minuscount % 2 !=0:
    for i in range(0,N,1):
        minabs = min(minabs,abs(A[i]))
    ans -= 2*minabs

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=0
ans=0
m=10**9+1
for i in a:
    if i<0: cnt+=1
    ans+=abs(i)
    if abs(i)<m: m=abs(i)
if cnt%2==0:
    print(ans)
else:
    print(ans-m*2)

Submission status: Accepted

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

min_abs = float('inf')
cnt = 0
for i in range(n):
    if a[i] < 0:
        cnt += 1
        a[i] *= -1
    min_abs = min(min_abs, a[i])

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