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:
N = int(input())                                                                                                                                             
A = list(map(int,input().split()))                                                                                                                           
                                                                                                                                                             
zc = 0                                                                                                                                                       
mc = 0                                                                                                                                                       
abs_min = float('inf')                                                                                                                                       
                                                                                                                                                             
sum_abs = 0                                                                                                                                                  
for a in A:                                                                                                                                                  
    if a == 0:                                                                                                                                               
        zc += 1                                                                                                                                              
    elif a <  0:                                                                                                                                             
        mc += 1                                                                                                                                              
                                                                                                                                                             
    if abs(a) < abs_min:                                                                                                                                     
        abs_min = abs(a)                                                                                                                                     
                                                                                                                                                             
    sum_abs += abs(a)                                                                                                                                        
                                                                                                                                                             
                                                                                                                                                             
if zc > 0 or mc % 2 == 0:                                                                                                                                    
    print(sum_abs)                                                                                                                                           
else:                                                                                                                                                        
    print(sum_abs-abs_min*2)

Submission status: Accepted

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

a = list(map(abs, l))
s = sum(a)

ptv = 0
ntv = 0
for x in l:
    if x > 0:
        ptv += 1
    elif x < 0:
        ntv += 1
        

if ntv % 2 == 0:
    print(s)
else:
    print(s-min(a)*2)

Submission status: Accepted

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

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

    for i, n in enumerate(A[1:-1], start=2):
        dp[i][0] = max(dp[i - 1][0] + n, dp[i - 1][1] - n)
        dp[i][1] = max(dp[i - 1][0] - n, dp[i - 1][1] + n)

    dp[-1] = [dp[N - 1][0] + A[-1], dp[N - 1][1] - A[-1]]

    print(max(dp[-1]))


if __name__ == '__main__':
    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

b = list(map(abs, a))

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

Submission status: Accepted

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

tmp = 10**11
tmp2 = 0
count =0 

for i in range(len(a)):
    if (abs(a[i]) < tmp):
        tmp = abs(a[i])
        tmp2 = i
        
    if a[i] < 0:
        count += 1
    
if count % 2 == 0:
    a = [abs(i) for i in a]
    print(sum(a))
else:
    a = [abs(i) for i in a]
    a[tmp2] = a[tmp2]* -1
    print(sum(a))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue May 14 10:45:22 2019

@author: avina
"""

N = int(input())
L = list(map(int, input().strip().split()))
dp = [[0,0] for i in range(N+1)]
dp[0][1] = -1e7
for i in range(N):
    dp[i+1][0] = max(dp[i][0] + L[i], dp[i][1] - L[i])
    dp[i+1][1] = max(dp[i][1] + L[i], dp[i][0] - L[i])

print(dp[N][0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = [int(v) for v in input().split(' ')]

# 負の数が偶数 -> 全部+にできる
# 負の数が奇数 -> どれか一つが-になる
# 負の数の偶奇チェック
sign = 1
for a in A:
    if a != 0:
        sign *= a/abs(a)

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

if sign > 0:
    print(sum(abs_A))
else:
    print(sum(abs_A)-min(abs_A)*2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 負整数が偶数個の場合は全て正整数に置き換えられ、奇数個の場合は少なくとも一つは負整数が残る
input()
num_list = list(map(int, input().split()))
minus_num = 0
sum = 0
for i in range(len(num_list)):
    if(num_list[i] < 0):
        minus_num += 1
        num_list[i] *= -1
    sum += num_list[i]
if(minus_num % 2 == 0):
    print(sum)
else:
    print(sum - min(num_list) * 2)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8


def main():
    N = int(input())
    la = list(map(int, input().split()))
    num_negative = sum(1 for a in la if a < 0)
    if num_negative % 2 == 0:
        print(sum(abs(a) for a in la))
    else:
        print(sum(abs(a) for a in la) - 2 * min(abs(a) for a in la))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Flipping Signs
https://atcoder.jp/contests/abc125/tasks/abc125_d

"""
import sys


def solve(N, array):
    nf, f = 0, float('-inf')
    for a in array:
        nf, f = max(nf+a, f-a), max(nf-a, f+a)
    return nf


def main(args):
    N = int(input())
    array = [int(a) for a in input().split()]
    ans = solve(N, array)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = sorted(map(abs, A))
if sum(x < 0 for x in A) % 2 == 0:
    print(sum(B))
else:
    print(sum(B[1:])-B[0])

Submission status: Accepted

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

Submission status: Accepted

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

minus = 0
plus_min = 1000000000
minus_max = -1000000000
total = 0

for j in range(N):
    if A[j] >= 0:
        plus_min = min(A[j],plus_min)
    else:
        minus_max = max(A[j],minus_max)
        minus += 1

    total += abs(A[j])

if minus % 2 == 0:
    print(total)
else:
    print(total-2*min(abs(minus_max),plus_min))

Submission status: Accepted

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

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

a = list(map(abs, a))
total = sum(a)

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

Submission status: Accepted

Solution code:

#_N = 5
#A = [10, -4, -8, -11, 3]
_N = int(input())
A = list(map(int, input().split(" ")))

n = len(list(filter(lambda a:a<=-1, A)))
a = list(map(abs, A))
res = sum(a)
if n % 2 == 1:
    res -= min(a) * 2
print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
count = 0
mina = abs(a[0])
ans = 0
zflag = False

for i in range(0,n):
    if a[i] == 0:
        zflag = True
        continue
    elif a[i] < 0:
        count += 1
        a[i] *= -1
    ans += a[i]
    mina = min(mina,a[i])

if zflag == False and count%2 == 1:
    ans -= 2*mina
print(ans)

Submission status: Accepted

Solution code:
import math
n = int(input())
M = list(map(int, input().split()))
p = [q < 0 for q in M].count(True)
X = [abs(x) for x in M]
if p % 2 == 0:
    print(sum(X))
else:
    print(sum(X) - min(X)*2)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
min_ = 1e9
flag = 0
ans = 0
for e in a:
  if e<0:
    flag = (flag+1) % 2
  if min_>abs(e):
    min_ = abs(e)
  ans += abs(e)
if flag:
  print(ans-min_*2)
else:
  print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
#print(n)
dp=[]
#print(dp)
dp+=[[0,-1234567890123]]
i=0
#print(a)
while i<n:
    
    i+=1
    dp+=[[0,0]]
    dp[i][0]= max(dp[i-1][0]+a[i-1],dp[i-1][1]-a[i-1])
    #print(dp)
    dp[i][1]= max(dp[i-1][0]-a[i-1],dp[i-1][1]+a[i-1])
    #print(dp)
print(dp[n][0])
#print(dp)

Submission status: Accepted

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

minusList = [i for i in A if i < 0]
absList = list(map(abs,A))
ans = sum(absList)
if len(minusList) % 2 != 0:
	minimum = min(absList)
	ans = ans - minimum*2

print(ans)

Submission status: Accepted

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

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

if a[n-1] >= 0:
    print(sum(a))
else:
    a[n-1] = -a[n-1]
    print(sum(a) - 2 * min(a))

Submission status: Accepted

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

sum = 0
cnt = 0
d = 1000000000
for i in a:
    if (i < 0):
        cnt += 1;
        sum -= i
        if (-i < d):
            d = -i
    elif (i >= 0):
        sum += i
        if (i < d):
            d = i

if (cnt % 2 == 1):
    sum -= 2 * d

print(sum)

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]+A[1]
dp[0][1]=-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]))

Submission status: Accepted

Solution code:
a=int(input())
b=list(map(int,input().split()))
c=list(filter(lambda n:n<=0,b))
c=list(map(lambda n:n*-1,c))
d=list(filter(lambda n:n>0,b))
ans=sum(d)+sum(c)
ansl=c+d
if len(c)%2!=0:  
  ans-=min(ansl)*2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [ int(v) for v in input().split() ]

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < -1e9 and v < 1e9: raise()

abs_list = [abs(v) for v in A]

total = sum( abs_list )
num_of_minus = sum([ True for v in A if v < 0 ])

if num_of_minus % 2 == 1:
    print(total - min( abs_list ) * 2)
else:
    print(total)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

N = int(input())
A = getlist()
j = 0
for i in range(N):
	if A[i] <= 0:
		j += 1
	A[i] = abs(A[i])

A = sorted(A)
if j % 2 == 0:
	print(sum(A))
else:
	print(sum(A) - 2 * A[0])

Submission status: Accepted

Solution code:

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

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < -1e9 and v < 1e9: raise()

abs_list = [abs(v) for v in A]

total = sum( abs_list )
num_of_minus = sum([ True for v in A if v < 0 ])

if num_of_minus % 2 == 1:
    print(total - min( abs_list ) * 2)
else:
    print(total)

Submission status: Accepted

Solution code:

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

neg_count = 0
A_abs = [0] * N
for i in range(0, N):
    if A[i] < 0:
        neg_count += 1
    A_abs[i] = abs(A[i])

Sum = sum(A_abs)
Min = min(A_abs)

if neg_count % 2 == 0:
    print(Sum)
else:
    print(Sum - 2*Min)

Submission status: Accepted

Solution code:
'''input
11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000
'''

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

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

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

Submission status: Accepted

Solution code:
a = int(input())
b = [int(i) for i in input().split()]
c = 0
d = []

for i in b:
    if i < 0:
        c += 1
    d.append(abs(i))

if c % 2 == 0:
    print(sum(d))
else:
    print(sum(d) - (min(d) * 2))

Submission status: Accepted

Solution code:
import numpy as np

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

"""
任意の2組みの数字の符号を変えることができる
したがって負の数が偶数個の場合全てを正にして総和をとれば良い
負の数が奇数個の場合絶対値の最小のもののみ負にして総和をとればよい
0が存在する場合はすべて正にできる
"""

A_abs = np.abs(A)

if 0 in A:
    print(np.sum(A_abs))

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

    if num % 2 == 0:
        print(np.sum(A_abs))
    else:
        print(np.sum(A_abs) - 2 * min(A_abs))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(raw_input())
a = map(int, raw_input().split())

memo = dict()
def dp(pos, flag):
  if pos == n - 1:
    if flag == 0:
      return a[pos]
    else:
      return -a[pos]
  if (pos, flag) in memo:
    return memo[(pos, flag)]
  elif flag == 0:
    memo[(pos, flag)] = max(dp(pos + 1, 0) + a[pos], dp(pos + 1, 1) - a[pos])
    return memo[(pos, flag)]
  else:
    memo[(pos, flag)] = max(dp(pos + 1, 0) - a[pos], dp(pos + 1, 1) + a[pos])
    return memo[(pos, flag)]
print dp(0, 0)

Submission status: Accepted

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

Submission status: Accepted

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

INF = 10**9

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

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

print(dp[N][0])

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
m,ans = 10**9,0
for i in range(n-1):
    m = min(m,abs(a[i]))
    if a[i] < 0:
        a[i]*=(-1)
        a[i+1]*=(-1)
if a[-1] >= 0:
    print(sum(a))
else:
    a[-1] *= (-1)
    m = min(m,abs(a[i+1]))
    print(sum(a)-m*2)

Submission status: Accepted

Solution code:
N = int(input())
li = [ int(it) for it in input().split() ]

sign = 1
for it in li:
  if (it<0):
    sign*=-1
    
li=[ abs(it) for it in li ]
li.sort()
if (sign==1):
  print (sum(li))
else:
  print (sum(li[1:])-li[0])

Submission status: Accepted

Solution code:
import bisect

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

idx = bisect.bisect_right(a,0)

res = -sum(a[:idx]) + sum(a[idx:])

if idx%2==1:
    if idx<n:
        c = min(abs(a[idx-1]), abs(a[idx]))
        res -= 2*c
    else:
        res -= 2*abs(a[idx-1])
        
print(res)

Submission status: Accepted

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

dp1 = []
dp2 = []

dp1.append(max(a[0] + a[1], -a[0] - a[1]))
dp2.append(max(-a[0] + a[1], a[0] - a[1]))

for i in range(2, n):
    dp1.append(max(dp1[-1] + a[i], dp2[-1] - a[i]))
    dp2.append(max(dp1[-2] - a[i], dp2[-1] + a[i])) # 上の行でappendしてるから直前の項は後ろから2番目

print(dp1[-1])

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
*a, = map(int, input().split())
b = np.abs(a)
#print(b)
print(np.sum(b)-2*np.min(b) if (np.sum(i<0 for i in a)%2) else np.sum(b))

Submission status: Accepted

Solution code:

n = int(input())
a = list(map(int,input().split()))
ma = []
pa = []
l =[]
t = 0
k  = 0
for i in a:
  if i < 0:
    ma.append(i)
    l.append(i*-1)
    k+=1
  elif i> 0:
    pa.append(i)
    l.append(i)
  else:
    t = 1
s = sum(l)
print(s  if t == 1 or k%2==0 else s - 2*min(l))

Submission status: Accepted

Solution code:
import numpy as np


if __name__ == '__main__':
  N = int(input())
  A = list(map(int, input().split()))

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

  if (num_of_minus % 2 == 0) or (sum([a == 0 for a in A])>0):
      print(ans)
  else:
      print(ans - 2 * min(abs_A))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
b=[i for i in a if i<0]

if len(b)%2==0:
    print(sum([abs(i) for i in a]))
else:
    c=[abs(i) for i in a]
    print(sum(c)-2*min(c))

Submission status: Accepted

Solution code:
import math
N=int(input())
s=input().split()
s_l=[]
i=0
count=0
while i<N:
       p=0
       q=0
       if int(s[i])<0:
              p=int(s[i])*(-1)
              s_l.append(p)
              count+=1
       else:
              q=int(s[i])
              s_l.append(q) 
       i+=1
ans1=sum(s_l)
ans2=sum(s_l)-min(s_l)*2

if count%2==0:
       print(ans1)
else:
       print(ans2)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0
Min=float('inf')
while True:
    if len(A)==0:
        break
    if A[-1]<0:
        break
    else:
        Min=A[-1]
        ans+=A[-1]
        A.pop()
if len(A)%2==1:
    if abs(A[-1])>Min:
        ans-=A[-1]+2*Min
    else:
        ans+=A[-1]
    A.pop()
ans+=-1*sum(A)
print(ans)

Submission status: Accepted

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

noon = 0
noz = 0
ms = 10**9
s = 0
for x in a:
    if x < 0:
        noon += 1
    elif x == 0:
        noz += 1
    ms = min(ms, abs(x))
    s += abs(x)

if noz == 0:
    if noon % 2 != 0:
        ans = s - 2 * ms
    else:
        ans = s
else:
    ans = s

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

m = 10**10
c = 0
s = 0
for a in al:
    m = min(m, abs(a))
    s += abs(a)
    if a<0:
        c += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def get_next_int():
    return int(float(input()))
def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])

def main():
    n = get_next_int()
    numbers = get_next_ints()
    
    minimum_number = abs(numbers[0])
    
    count_of_minus = 0
    total = 0
    
    for number in numbers:
        if number < 0:
            count_of_minus += 1
        abs_number = abs(number)
        total += abs_number
        if abs_number < minimum_number:
            minimum_number = abs_number
        
    if count_of_minus % 2 == 1:
        total -= minimum_number * 2
    
    print(total)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
import sys

""""
import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


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

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

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

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

def main():
    Aabs = [0]*N
    cnt_n=0
    for i,a in enumerate(A):
        Aabs[i] = abs(a)
        if a <0:
            cnt_n+=1
    if cnt_n%2 ==0:
        print(sum(Aabs))
    else:
        print(sum(Aabs)- min(Aabs)*2)
            
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
counter = 0
summention = 0
minus = []
for i in range(n):
    if a[i] < 0:
        summention += -a[i]
        counter += 1
        minus.append(-a[i])
    else:
        summention += a[i]
        minus.append(a[i])

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

Submission status: Accepted

Solution code:

# coding: utf-8

# In[28]:

import sys
#input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))


# In[21]:

#import numpy as np
#A.sort(key=lambda x:abs(x))
#print(N, A)


# In[25]:

#A = np.array(A)
#print(sum(A<0))
#if sum(A<0)%2 == 0:
#    print(sum(abs(A)))
#else:
#    print(sum(abs(A[1:])) - abs(A[0]))


# In[29]:

B = list(map(abs, A))
C = [a for a in A if a < 0]
#print(A)
#print(B)
#print(C)


# In[30]:

if len(C)%2 ==0:
    print(sum(B))
else:
    print(sum(B) - min(B)*2)


# In[ ]:

Submission status: Accepted

Solution code:

# coding: utf-8

# In[20]:

import sys
#input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))


# In[21]:

import numpy as np
A.sort(key=lambda x:abs(x))
#print(N, A)


# In[25]:

A = np.array(A)
#print(sum(A<0))
if sum(A<0)%2 == 0:
    print(sum(abs(A)))
else:
    print(sum(abs(A[1:])) - abs(A[0]))


# In[ ]:

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

N = int(input())
data = list(map(int, input().split(" ")))

minus_num = sum([x < 0 for x in data])
abs_data = list(map(abs, data))
if minus_num%2 == 0:
    # すべて正の数に変換
    print(sum(abs_data))
else:
    # 一つだけ負の数
    min_data = min(abs_data)
    print(sum(abs_data) - 2*min_data)

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
    A[i]=-A[i]
if count%2==0:
  print(sum(A))
else :
  print(sum(A)-2*min(A))

Submission status: Accepted

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

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

if N > 2:
	for i in range(2, 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-1]*2-A[i], dp[i-1][1]+A[i-1]*2-A[i])

print(max(dp[-1]))

Submission status: Accepted

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

if 0 in a:
    ans = 0
    for x in a:
        ans += abs(x)
    print(ans)
    exit()

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

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

Submission status: Accepted

Solution code:
N = int(input())
As = []
minus = 0
for c in input().split(" "):
  tmp = int(c)
  if tmp<0:
    minus += 1
    As.append(-tmp)
  else:
    As.append(tmp)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split(" ")))
if len(list(filter(lambda x: x < 0, a))) % 2 == 0:
    print(sum(list(map(abs, a))))
else:
    a = list(map(abs, a))
    print(sum(a) - min(a)*2)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
DP = [[0 for _ in range(2)]for _ in range(N-1)]
## 0:non operation ,1:operated

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