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:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  dp=[0,-10**18]
  for i in range(n-1):
    dp2=[max(dp[0]+a[i],dp[1]-a[i]),max(dp[0]-a[i],dp[1]+a[i])]
    dp=dp2
  print(max(dp[0]+a[-1],dp[1]-a[-1]))
main()

Submission status: Accepted

Solution code:
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
A.sort()
if cnt % 2 == 1:
    print(sum(A[1:])-A[0])
else:
    print(sum(A))

Submission status: Accepted

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

Submission status: Accepted

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

cnt, ans, num = 0, 0, 10 ** 10
for ai in a:
    cnt += (ai < 0)
    ans += abs(ai)
    num = min(num, abs(ai))
print(ans if cnt % 2 == 0 else ans - 2 * num)

Submission status: Accepted

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

# 全ての値の合計を求め、負の値が偶数個であれば全ての値は非負の値にできる為、合計値を出力
# 負の値の数が奇数個の場合は1つだけが負の値になる為、この場合は最小値を負の値にして合計を出力
ans = 0
count = 0
for i in range(n):
  if a[i] < 0: count += 1 # 負の値をカウント
  a[i] = abs(a[i])
  ans += a[i] # 全ての値を足していく
if count%2 == 0: print(ans) # 負の値が偶数個であればそのまま出力
else:
  ans -= 2*min(a) # 負の値が奇数個であれば最小値の値分減らして出力
  print(ans)

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int, input().split()))
cnt = 0
flg = False
for i in range(N):
    if arr[i] == 0:
        flg = True
    if arr[i] < 0:
        cnt += 1
    arr[i] = abs(arr[i])
if cnt % 2 == 0 or flg:
    print(sum(arr))
else:
    print(sum(arr) - min(arr)*2)

Submission status: Accepted

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

minus_cnt = 0
abs_sum = 0
min_abs_val = 1000000000
for i in range(N):
    val = A[i]
    abs_val = abs(val)
    abs_sum += abs_val
    if abs_val < min_abs_val:
        min_abs_val = abs_val
    if val < 0:
        minus_cnt += 1

B_max_sum = abs_sum
if minus_cnt % 2 != 0:
    B_max_sum -= (min_abs_val * 2)

print(B_max_sum)

Submission status: Accepted

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

minus_cnt = 0
abs_sum = 0
min_abs_val = 1000000000
for i in range(N):
    val = A[i]
    abs_val = abs(val)
    abs_sum += abs_val
    if abs_val < min_abs_val:
        min_abs_val = abs_val
    if val < 0:
        minus_cnt += 1

B_max_sum = abs_sum
if (minus_cnt % 2 != 0) and (min_abs_val != 0):
    B_max_sum -= (min_abs_val * 2)

print(B_max_sum)

Submission status: Accepted

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

minus_cnt = 0
abs_sum = 0
min_abs_val = 1000000000
for i in range(N):
    abs_val = abs(A[i])
    abs_sum = abs_sum + abs_val
    if abs_val < min_abs_val:
        min_abs_val = abs_val
    if A[i] < 0:
        minus_cnt = minus_cnt + 1

B_max_sum = 0
if (minus_cnt % 2 == 0) or (min_abs_val == 0):
    B_max_sum = abs_sum
else:
    B_max_sum = abs_sum - min_abs_val * 2

print(B_max_sum)

Submission status: Accepted

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

a.sort()
minus = n
for i in range(n):
  if a[i] >= 0:
    minus = i
    break

a = list(map(abs, a))
a.sort()

if minus % 2 == 0:
  print(sum(a))
else:
  print(sum(a) - 2 * a[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a=sorted(map(int,input().split()))
    aa=sorted(abs(i) for i in a)
    
    if sum(i<0 for i in a)%2==0:
        print(sum(aa))
    else:
        print(-aa[0]+sum(aa[1:]))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(max(dp[0][n-1],dp[1][n-1]))

Submission status: Accepted

Solution code:
#a, b, k = map(int, input().split( ))
n = int(input())
A = list(map(int,input().split()))

s = 0
m = 10**9
nimus = 0
for a in A:
  s += abs(a)
  m = min(m,abs(a))
  if a <0:
    nimus += 1

if nimus%2 == 0:
  print(s)
else:
  print(s-2*m)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=0#負数の数
ab=10**10#絶対値の最小
s=0#絶対値の総和
for i in range(n):
    if a[i]<0:
        c+=1
    if ab>abs(a[i]):
        ab=abs(a[i])
    s+=abs(a[i])
if c%2==0:
    print(s)
else:
    print(s-2*ab)

Submission status: Accepted

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

DP = [[0 for _ in range(2)] for _ in range(N)]
DP[0][1] = -INF

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

Submission status: Accepted

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

cnt_neg = sum(a < 0 for a in A)
cnt_zero = A.count(0)

if cnt_zero or cnt_neg % 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:
import math

n = int(input())
aL = list(map(int, input().split(" ")))

mc = 0
for a in aL:
    if a < 0:
        mc += 1

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

if mc % 2 == 0:
    print(sum(aL))
else:
    print(sum(aL) - (2 * min(aL)))

Submission status: Accepted

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

cnt = 0
A_ = []
for i in A:
    if i < 0:
        cnt += 1
        A_.append(-i)
    else:
        A_.append(i)

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

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = LI()
    A_abs = [abs(i) for i in A]

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

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

minus=0
for i in a:
  if i<0:
    minus+=1
    
if minus%2==1:
  print(sum(b)-min(b)*2)
else:
  print(sum(b))

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
dp = [[0]*2 for _ in range(N)]
dp[0][1] = -10**18

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

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

Submission status: Accepted

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

a.sort()
s=sum(a)
ans=[]
ans.append(s)
N=n//2

for i in range(1,N+1):
  x=i*2-1
  y=i*2
  s+=a[x-1]*-2
  s+=a[y-1]*-2
  ans.append(s)
  
print(max(ans))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
answer=0
if 0 in A:
    for a in A:
        answer+=abs(a)
    print(answer)
else:
    minus=0
    plus=0
    for a in A:
        if a<0:
            minus+=1
        else:
            plus+=1
    if minus%2==0:
        for a in A:
            answer+=abs(a)
        print(answer)
    else:
        B=[]
        for a in A:
            B.append(abs(a))
        place=B.index(min(B))
        for n in range(N):
            if n==place:
                answer-=abs(A[n])
            else:
                answer+=abs(A[n])
        print(answer)

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  A = list(map(int, input().split()))
  B = [abs(a) for a in A]
  ans = sum(B)
  under = [a for a in A if a<0]
  if len(under)%2==1:
    ans -= min(B)*2
  return ans
print(solve())

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[0,0] for i in range(n)]
dp[0][0]=a[0]
dp[1][0]=dp[0][0]+a[1]
dp[1][1]=dp[0][0]-2*a[0]-a[1]
for i in range(2,n):
    dp[i][0]=max(dp[i-1])+a[i]
    dp[i][1]=max(dp[i-1][0]-2*a[i-1]-a[i],dp[i-1][1]+2*a[i-1]-a[i])
print(max(dp[n-1]))

Submission status: Accepted

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

Submission status: Accepted

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

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

if 0 in lis or minus % 2 == 0:
    print(sum(lis))
else:
    print(sum(lis) - 2*min(lis))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#print(cnt_fu,cnt_0,ans,b)
if cnt_fu%2==0:
    print(ans)
else:
    print(ans-min(b)*2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: UTF-8
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#print(A)
for a in A:
    if a < 0:
        min_cnt += 1
    ans += abs(a)
#print(min_cnt)
if min_cnt % 2 == 1:
    ans -= 2 * abs_A[0]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
#    print(i,min,total)
if minus %2 == 0 :
    print(total)
else :
    print(total-min*2)

Submission status: Accepted

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

Submission status: Accepted

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

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)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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()

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    # dp[1]: flipped
    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])


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

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

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# from pprint import pprint
# import math
# import collections
import numpy as np

n = int(input())
# n, k = map(int, input().split(' '))
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)