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 sys import exit

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

dp = [[0] * 2 for i in range(N + 1)]
dp[0][0] = 0
dp[0][1] = -10 ** 6

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

print(dp[N][0])

Submission status: Accepted

Solution code:
from sys import exit

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

zero = False
negative_num = 0
min_num = abs(A[0])

for a in A:
    if a == 0:
        zero = True
        break

    if a < 0:
        negative_num += 1

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

ans = 0

if zero or (negative_num % 2 == 0):
    for a in A:
        ans += abs(a)
else:
    for a in A:
        ans += abs(a)
    ans -= min_num * 2

print(ans)

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

INF = 10**6

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

Submission status: Accepted

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

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

dp[0][1] = - 10 ** 18

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

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

Submission status: Accepted

Solution code:
# import sys  sys.exit()を使う時に必要

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    # A, B, C = input().split()
    A = [int(i) for i in input().split()] 
    # S = [input() for _ in range(N)]  縦持ち／行数N
    # t = [0] * N  　　ti xi yi 縦持ち/行数N
    # x = [0] * N
    # y = [0] * N
    # for i in range(N):
    #   t[i], x[i], y[i] = map(int, input().split())
  else:
    #A = [-10,5,-4]
    #A = [10,-4,-8,-11,3]
    A = [-1000000000,1000000000,-1000000000,1000000000,-1000000000,0,1000000000,-1000000000,1000000000,-1000000000,1000000000]
    N = len(A)

  # Processing
  # if 'get_ipython' in globals(): print("debug")
  sumA = 0
  min_abs = 1000000000
  cnt_minus = 0
  for a in A:
    if a < 0 :
      cnt_minus +=1
    if abs(a) < min_abs: 
      min_abs = abs(a)
    sumA += abs(a)
  
  if cnt_minus % 2 > 0:
    sumA -= min_abs * 2
  
  print(sumA)

main()

Submission status: Accepted

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

minv = -1
count = 0
s = 0
for i in range(n):
    if a[i] < 0:
        s += -a[i]
        if minv > -a[i] or minv == -1:
            minv = -a[i]
        count += 1
    else:
        s += a[i]
        if minv > a[i] or minv == -1:
            minv = a[i]

if count % 2 == 1:
    s += 2*(-minv)

print(s)

Submission status: Accepted

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

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

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

n_neg = sum([1 for i in range(n) if a[i] < 0])
if n_neg%2 == 0:
    ans = sum([abs(aa) for aa in a])
else:
    min_abs = min([abs(aa) for aa in a])
    ans = sum([abs(aa) for aa in a]) - 2*min_abs
print(ans)

Submission status: Accepted

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

s = 0
c = 0
m = abs(a[0])
for i in range(n):
  t = abs(a[i])
  s += t
  if m > t:
    m = t
  if a[i] < 0:
    c += 1

if c % 2 == 1:
  s -= m * 2

print(s)

Submission status: Accepted

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

from collections import deque
import heapq
import math
import bisect


def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[-1]*2 for i in range(N+1)]

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

abs_a = list(map(abs, a[:]))
s = sum(abs_a[:])
m = len([i for i in a if i < 0])
if m % 2 == 0:
  print(s)
else:
  print(s - 2 * min(abs_a))

Submission status: Accepted

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

Submission status: Accepted

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

n = int(input())
x = list(map(int, input().split()))
mc = 0
m = 1000000001

for v in range(n):
    t = x[v]
    if t < 0:
        mc += 1
    
    m = min(m, abs(t))

if mc % 2 == 0:
    s = 0
    for v in range(n):
        s += abs(x[v])
    print(s)
else:
    s = 0
    for v in range(n):
        t = abs(x[v])
        if t == m:
            s -= t
        else:
            s += t
            
    print(s)

Submission status: Accepted

Solution code:
n = int(input())

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

if len([i for i in l if i < 0]) % 2 == 0:
  data = [abs(x) for x in l]
  print(sum(int(i) for i in data))
else:
  data = [abs(x) for x in l]
  print(sum(int(i) for i in data) - 2*min(data))

Submission status: Accepted

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

cnt = 0
min = 10000000000
for i in range(n):
    if x[i] < 0:
        cnt += 1
    if abs(x[i]) < min:
        min = abs(x[i])

if 0 in x:
    cnt = 0

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

#print(cnt)
#print(ans)

if cnt % 2 == 0:
    print(ans)

else:
    print(ans - min*2)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a_abs = [abs(i) for i in a]
if len([i for i in a if i < 0]) % 2 == 0:
  ans = sum(a_abs)
else:
  ans = sum(a_abs) - min(a_abs) * 2
print(ans)

Submission status: Accepted

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

def solve(N: int, A: "List[int]"):
    minus_count = 0
    
    for i in range(N):
        if A[i] < 0:
            minus_count += 1

    if minus_count % 2 == 0:
        result = sum([abs(x) for x in A])
    else:
        min_A = 10000000
        min_idx = -1
        for i, x in enumerate(A):
            if abs(x) < min_A:
                min_A = abs(x)
                min_idx = i
        result = 0
        for i, x in enumerate(A):
            if i == min_idx:
                result += abs(x) * -1
            else:
                result += abs(x)
    print(result)
    return

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

has_zero = 0 in As
num_of_minus = len(list(filter(lambda x: x<0, As)))

abss = list(map(abs, As))
ans = sum(abss)
if num_of_minus%2 != 0:
    ans -= min(abss) * 2
    
print(ans)

Submission status: Accepted

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

ans = sum(abs(ai) for ai in a)

if sum(ai < 0 for ai in a) % 2:
    ans -= 2 * min(abs(ai) for ai in a)

print(ans)

Submission status: Accepted

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

minus_cnt = len([i for i in a if i < 0])

a_abs = [abs(i) for i in a]
if minus_cnt%2 == 0:
  ans = sum(a_abs)
else:
  ans = sum(a_abs) - min(a_abs)*2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A= [int(a) for a in input().split()]
minusnum=sum(a<0 for a in A)
ablist=[abs(a) for a in A]
ans=sum(ablist)
if minusnum%2:
    ans=ans-2*min(ablist)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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


if counter & 1 == 1:
    print(sum(b) - min(b) * 2)
else:
    print(sum(b))

Submission status: Accepted

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

cnt = len([1 for i in range(N) if A[i] < 0])
SUM = sum(map(abs,A))
MIN = min(map(abs,A))

if cnt%2 == 0:
    print(SUM)
else:
    print(SUM-2*MIN)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt = 0
allsei = False
for i in range(n):
    if a[i] == 0:
        allsei = True
        break
    if a[i] < 0:
        cnt += 1
if cnt%2 == 0:
    allsei = True

ans = 0
mini =12345678901
for i in range(n):
    ans += abs(a[i])
    mini = min(mini,abs(a[i]))
if not allsei:
    ans -= 2*mini
print(ans)

Submission status: Accepted

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

min_abs = 10 ** 9 + 1
sum_abs = 0
cnt_neg = 0
for i in range(n):
  a_abs = a[i] if a[i] > 0 else - a[i]
  sum_abs += a_abs
  min_abs = min(min_abs, a_abs)
  if a[i] < 0:
    cnt_neg += 1
if cnt_neg % 2:
  print(sum_abs - 2 * min_abs)
else:
  print(sum_abs)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
total = 0
X = [0]*N
flag = False
subcount = 0

for i in range(N):
    if A[i] == 0:
        flag = True
    elif A[i] < 0:
        subcount += 1
    X[i] = abs(A[i])
    total += X[i]

if flag or (subcount % 2 == 0):
    print(total)
else:
    print(total-2*min(X))

Submission status: Accepted

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

i = bisect_left(a, 0)
if i % 2==0:
    print(sum(b))
else:
    print(sum(b) - 2*b[0])

Submission status: Accepted

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

Submission status: Accepted

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

n=0
sm=0
if A[0]>0:
  mn=A[0]
else:
  mn=(-1)*A[0]


for i in range(0,N):
  if A[i]<0:
    n=n+1
    sm=sm-A[i]
    if (-1)*A[i]<mn:
      mn=(-1)*A[i]
  else:
    sm=sm+A[i]
    if A[i]<mn:
      mn=A[i]
if n%2==0:
  print(sm)
else:
  print(sm-2*mn)

Submission status: Accepted

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

minus_count = 0
max_minus = -1145141919
min_plus = 1145141919
ans = 0
for a in A:
    ans += abs(a)
    if a < 0:
        minus_count += 1
        if max_minus < a:
            max_minus = a
    else:
        if min_plus > a:
            min_plus = a

if minus_count % 2 == 1:
    if -min_plus < max_minus:
        ans += 2*max_minus
    else:
        ans += -2*min_plus

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)
plus.sort()
minus.sort(reverse=True)

if len(plus)==0:
    if len(minus)%2==0:
        print(-sum(minus))
    else:
        print(-sum(minus)+2*minus[0])
    exit()

if len(minus)==0:
    print(sum(a))
    exit()

if len(minus) % 2==0:
    print(sum(plus) - sum(minus))
    exit()

if - minus[0] < plus[0]:
    print(sum(plus) - sum(minus) +2*minus[0])
else:
    print(sum(plus) - sum(minus) -2*plus[0])

Submission status: Accepted

Solution code:
n = int(input())
A = list(int(i) for i in (input().split()))

cnt = 0
tmp_sum = 0
minimum = 1000000000
for i in range(n):
  if(A[i] <= 0):
    cnt += 1
    tmp_sum = tmp_sum - A[i]
    if(minimum > A[i] * (-1)):
      minimum = A[i] * (-1)
  elif(A[i] > 0):
    tmp_sum = tmp_sum + A[i]
    if(minimum > A[i]):
      minimum = A[i]
if((cnt % 2) == 1):
  sum = tmp_sum - minimum * 2
else:
  sum = tmp_sum
print(sum)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
answer = 0
tmp = abs(a[0])
check = 0

for b in a:
    if b == 0:
        check += 1
        tmp = 0
    else:
        if b < 0:
            check += 1
        b = abs(b)
        if b < tmp:
            tmp = b
            answer += tmp
        else:
            answer += b
if check % 2 == 1:
    answer -= 2*tmp
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
#N = 5
#A = [10, -4, -8, -11, 3]

num_minus = 0
for i in A:
    if i < 0:
        num_minus +=  1
        
A_abs = [abs(i) for i in A]
if num_minus % 2 == 0:
    print(sum(A_abs))
else:
    print(sum(A_abs)- 2*min(A_abs))

Submission status: Accepted

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

i = 0
while i < n - 1:
    if a[i] <= 0:
        a[i] *= -1
        a[i+1] *= -1
    i += 1

s_a = sorted(a)

if s_a[0] < 0 and abs(s_a[0]) > s_a[1]:
    s_a[0] *= -1
    s_a[1] *= -1
    print(sum(s_a))
else:
    print(sum(s_a))

Submission status: Accepted

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

dp =[[0, -10**9]]
#print(dp[0][0])

for i in range(1,n+1):
	dp.append([max(dp[i-1][0]+ai[i-1], dp[i-1][1]-ai[i-1]), \
			max(dp[i-1][0]-ai[i-1], dp[i-1][1]+ai[i-1])])
	#print(dp)
    
print(dp[n][0])

Submission status: Accepted

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

minus_list = filter(lambda x: x<0,A)
minus_cnt = len(list(minus_list))

abs_list = list(map(abs,A))

if minus_cnt % 2 == 0:
    print(sum(abs_list))
else:
    print(sum(abs_list) - 2* min(abs_list))

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
B=[abs(i) for i in A]
minus=0
for i in A:
    if i<0:
        minus+=1
if minus%2==0:
    print(sum(B))
else:
    print(sum(B)-2*min(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
    A[i] *= -1
print(sum(A) if count % 2 == 0 else sum(A) - min(A) * 2)

Submission status: Accepted

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

count = 0
absmin = abs(A[0])

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

if count % 2 == 0:
  print(sum(A))
else:
  print(sum(A) - 2 * absmin)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N = d_in()
A_list = np.array(ds_in())
abs_A = np.abs(A_list)

ans = abs_A.sum()

if (A_list < 0).sum() % 2 == 0:
    print(ans)
else:
    print(ans - min(abs_A)*2)

Submission status: Accepted

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


minuscount = 0
abss = []
for i in a:
	abss.append(abs(i))
	if (i < 0):
		minuscount += 1

if minuscount % 2 == 0:
	print (sum(abss))
else :
	print (sum(abss) - 2 * min(abss))

Submission status: Accepted

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

Submission status: Accepted

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

cnt = len(list(filter(lambda x: x < 0, A)))


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

Submission status: Accepted

Solution code:
import numpy as np

n=int(input())
a=[int(i) for i in input().split()]
sign=0
ans=0
for i in range(n):
    if a[i]<0:
        a[i]=-1*a[i]
        sign+=1
m=min(a)
if sign%2==1:
    ans=sum(a)-2*m
else:
    ans=sum(a)
print(ans)

Submission status: Accepted

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

ans = 0
j = 0
B = list(map(abs,A))

for a in A:
    if a <= 0:
        j += 1
ans = sum(B)
if j%2 == 1:
    k = min(B)
    ans -= 2*k
print(ans)

Submission status: Accepted

Solution code:
input()
a = [int(i) for i in input().split()]
print(sum(map(lambda x:abs(x), a))-(0 if sum(map(lambda x:1 if x < 0 else 0, a))%2==0 else 2)*(min(map(lambda x:abs(x), a))))

Submission status: Accepted

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

ans = 0
j = 0
B = list(map(abs,A))

for a in A:
    if a < 0:
        j += 1
ans = sum(B)
if j%2 == 1:
    k = min(B)
    ans -= 2*k
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
abs_sum = 0
abs_min = 10 ** 10
minus_count = 0
for i in range(N):
    if A[i] < 0:
        minus_count += 1
    a_abs = abs(A[i])
    abs_sum += a_abs
    abs_min = min(abs_min, a_abs)
if minus_count % 2 == 0:
    print(abs_sum)
else:
    print(abs_sum - abs_min * 2)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc125
# -*- coding: utf-8 -*-

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

total = 0
minus = 0
minimum = abs(a[0])

for v in a:
        total += abs(v)
        if v < 0 :
                minus += 1
        if abs(v) < minimum:
                minimum = abs(v)

if minus%2 is 1:
        total -= minimum*2

print(total)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = sorted(list(map(int, input().split())))
i = bisect.bisect_left(a,0)
if i % 2 == 0:
    ans = abs(sum(a[:i]))+sum(a[i:])
else:
    if i == n:
        ans = abs(sum(a[:i-1]))+a[i-1]
    else:
        ans = abs(sum(a[:i-1]))+abs(a[i]+a[i-1])+sum(a[i+1:])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math
# import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))

def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]

n, a = II(), LI()
a_abs = list(map(abs,a))
print(sum(a_abs)) if sum(x < 0 for x in a) % 2 == 0 else print(sum(a_abs) - 2 * min(a_abs))

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math
# import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))

def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]

n, a = II(), LI()
a_abs = [abs(i) for i in a]
print(sum(a_abs)) if sum(x < 0 for x in a) % 2 == 0 else print(sum(a_abs) - 2 * min(a_abs))

Submission status: Accepted

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

under_zero_count = sum([i < 0 for i in A])

ans = 0
if under_zero_count % 2 == 0:
    for i in range(N):
        ans += abs(A[i])
    print(ans)
else:
    abs_list = []
    for i in range(N):
        abs_list.append(abs(A[i]))
    print(sum(abs_list) - min(abs_list)*2)

Submission status: Accepted

Solution code:
from sys import stdin

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

minus_cnt = len([x for x in A if x < 0])

res = 0

if minus_cnt % 2 == 0:
    res = sum(A_abs)
else:
    res = sum(A_abs) - 2*min(A_abs)

print(res)

Submission status: Accepted

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

absAList = [abs(i) for i in AList]
ans = sum(absAList)
if len([i for i in AList if i < 0]) % 2 == 1:
    ans -= min(absAList) * 2

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
dp = [[0 for i in range(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 = map(int,input().split())
alists = []
num = 0

for i in a:
    alists.append(abs(i))
    if i < 0:
        num = num + 1
        
if num % 2 == 1:
    print(sum(alists)-min(alists)*2)
else:
    print(sum(alists))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[i for i in a if i<1]
ans=0;k=0
if len(b)%2==0:
    for i in a:ans+=abs(i)
else:
  c=sorted([abs(i) for i in a]);l=c[0]
  for i in a:
    if (i==l or i==-l) and k==0:
      ans=ans+l if l<0 else ans-l
      k+=1
    else:
      ans+=abs(i)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
x = int(input())
y = list(map(int, input().split(" ")))

for i in range(x - 1):
  if y[i] < 0:
    y[i] *=-1
    y[i + 1] *=-1

if y[-1] < 0 and abs(min(y[0:-1])) < abs(y[-1]) :
  y[-1] *= -1
  y[y.index(min(y[0:-1]))] *= -1

print(sum(y))

Submission status: Accepted

Solution code:
import numpy
from operator import add
from functools import reduce

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

minus_num = 0
abs_A = []
for a in A:
    if a < 0:
        minus_num += 1
    abs_A.append(numpy.abs(a))

if minus_num % 2 == 0:
    print(reduce(add, abs_A))
else:
    abs_A.sort()
    print(reduce(add, abs_A[1:])-abs_A[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

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

count = 0
s = 0
b = []
for i in range(n):
    count += 1 if a[i] < 0 else 0
    b.append(abs(a[i]))
flg = False
if count % 2 == 1:
    flg = True
ans = sum(b)
if flg:
    ans -= min(b) * 2
print(ans)

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

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

dp = [[0 for i in range(2)] for i in range(n + 1)]
dp[0][1] = float('inf') * -1

for i in range(n):
    dp[i + 1][0] = max(dp[i][0] + a[i], dp[i][1] - a[i])
    dp[i + 1][1] = max(dp[i][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()))
n_minus=sum([a<0 for a in A])
abs_A=[abs(a) for a in A]
ans=sum(abs_A)
if n_minus%2==0:
        print(ans)
else:
        print(ans-2*min(abs_A))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

inf = float('inf')

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

dp = np.empty((N + 1, 2))
dp[0][0] = 0
dp[0][1] = -inf
# dp[i][0]:=1-indexedで、a_iとa_i+1を反転させない場合の最大値
# dp[i][1]:=1-indexedで、a_iとa_i+1を反転させる場合の最大値

for i, aa in enumerate(a, 0):
    dp[i + 1][0] = max(dp[i][0] + aa, dp[i][1] - aa)
    dp[i + 1][1] = max(dp[i][0] - aa, dp[i][1] + aa)
print(int(dp[N][0]))
# np.emptyのせいか、float型になっているので、WA扱いになる

# np.zerosよりも、np.emptyの方が速い？

Submission status: Accepted

Solution code:
import numpy as np

inf = float('inf')

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

dp = np.zeros((N + 1, 2))
dp[0][1] = -inf
# dp[i][0]:=1-indexedで、a_iとa_i+1を反転させない場合の最大値
# dp[i][1]:=1-indexedで、a_iとa_i+1を反転させる場合の最大値

for i, aa in enumerate(a, 0):
    dp[i + 1][0] = max(dp[i][0] + aa, dp[i][1] - aa)
    dp[i + 1][1] = max(dp[i][0] - aa, dp[i][1] + aa)
print(int(dp[N][0]))

Submission status: Accepted

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

dp0 = [0] * N
dp1 = [0] * N
dp0[0] = a[0]
dp1[0] = -(10 ** 10)
for i in range(1, N):
    dp0[i] = max(dp0[i - 1] + a[i], dp1[i - 1] + a[i])
    dp1[i] = max(dp0[i - 1] - 2 * a[i - 1] - a[i], dp1[i - 1] + 2 * a[i - 1] - a[i])

print(max(dp0[N - 1], dp1[N - 1]))

Submission status: Accepted

Solution code:
n=int(input())
a_n=list(map(int,input().split()))
count=0
ans=0
for i in a_n:
  if i <0:
    count +=1

def fun():
  tmp_ans=0
  for i in a_n:
    if i<0:
      tmp_ans += -1*i
    else:
      tmp_ans += i
  return tmp_ans

if count%2==0:
  ans = fun()
else:
  tmp=abs(a_n[0])
  for i in a_n:
    if tmp > abs(i):
      tmp = abs(i)
  
  ans =fun()-2*tmp
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a_n=list(map(int,input().split()))
count=0
ans=0
for i in a_n:
  if i <0:
    count +=1

if count%2==0:
  for i in a_n:
    if i<0:
      ans += -1*i
    else:
      ans += i
else:
  tmp=abs(a_n[0])
  for i in a_n:
    if tmp > abs(i):
      tmp = abs(i)
  for i in a_n:
    if i <0:
      ans +=-1*i
    else:
      ans +=i
  ans -=2*tmp
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
ans=0
m=100000000000
p=0
for i in a:
    if i<0:
        p+=1
    m=min(m,abs(i))
    ans+=abs(i)

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