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:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = iip()
    A.sort()

    nm = 0
    for i in A:
        if i < 0:
            nm += 1

    A = [abs(i) for i in A]
    if nm % 2 == 0:
        print(sum(A))
    else:
        A.sort()
        #print(A)
        print(sum(A) - 2*A[0])


#####################################################ライブラリ集ここから

def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# library
# -------------------------------------------------------------



# -------------------------------------------------------------
# main
# -------------------------------------------------------------
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==0:
    print(sum(A))
else:
    print(sum(A)- A[0]*2)

Submission status: Accepted

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
su=0
mi=float("inf")
micount=0
for i in range(N):
    su=su+abs(A[i])
    if A[i]<0:
        micount=micount+1
    if mi>abs(A[i]):
        mi=abs(A[i])
if micount%2==1:
    su=su-2*mi
print(su)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

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

neg_cnt = 0
minimum = 10**10
for num in A:
    minimum = min(minimum, abs(num))
    if num < 0:
        neg_cnt += 1
        
ans = 0
for num in A:
    if num < 0:
        ans += -num
    else:
        ans += num 

if neg_cnt % 2 == 0:
    print(ans)               
else:
    print(ans - minimum * 2)

Submission status: Accepted

Solution code:
import numpy as np
import sys
n = int(input())
a = np.array([int(x) for x in input().split()])
dp = np.zeros((n + 1, 2))
dp[0][1] = -2000000001
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(int(dp[n][0]))

Submission status: Accepted

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

dp= [[0,0] for _ in range(N+1)]
dp[0] = [0, -float("inf")]
#print(type(dp[0][0]))

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(x) for x in input().split()]
ans = 0
min_num = int(1e10)
odd_num = 0
for a in A:
    if a < 0:
        odd_num += 1
    a = abs(a)
    ans, min_num = ans + a, min(min_num, a)
if odd_num % 2 == 0:
    print(ans)
else:
    print(ans - min_num * 2)

Submission status: Accepted

Solution code:
import math

n = int(input())
a_list = [int(i) for i in input().split()]
sum = 0
ans = 0
mini = 10000000000
count = 0
for i in range(n):
    if a_list[i]<0:
        count += 1
    mini = min(mini,abs(a_list[i]))
    sum += abs(a_list[i])

if count%2==1:
    print(sum - 2*mini)
else:
    print(sum)

Submission status: Accepted

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

su = sum(map(abs, a))
li = [i for i in a if i<0]

if len(li)%2 != 0 and 0 not in a:
    su -=2*min(map(abs, a))

print(su)

Submission status: Accepted

Solution code:
# reference: https://img.atcoder.jp/abc125/editorial.pdf
N = int(input())
A = list(map(int, input().split()))

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

print(dp[N][0])

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
S=0
cnt=0 #マイナスの個数
m=10**10 #絶対値の最小値
for a in A:
    S+=abs(a)
    m=min(abs(a),m)
    if a<0:
        cnt+=1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0 for j in range(2)] for i in range(n+1)]
inf = 10**9+7
dp[1][0], dp[1][1] = a[0], -a[0]
for i in range(1, 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])
ans = max(dp[n-1][0]+a[-1], dp[n-1][1]-a[-1])
print(ans)

Submission status: Accepted

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    negatives = sum((1 if x < 0 else 0) for x in a)
    if negatives % 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))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

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

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

ans = 0
min_val = 10**10
if minus_cnt % 2 == 0:
    for i in range(N):
        ans += abs(A[i])
else:
    for i in range(N):
        ans += abs(A[i])
        min_val = min(min_val, abs(A[i]))
    ans -= min_val * 2

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    A = Scanner.map_int()
    minus = sum([a < 0 for a in A])
    ans = sum([abs(a) for a in A])
    if minus % 2 == 1:
        ans -= min([abs(a) for a in A]) * 2
    print(ans)


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
if min(a)>=0:
  print(sum(a))
  exit()
b=[abs(a[i]) for i in range(n)]
s=sum(b)
if cnt%2==0:
  print(s)
  exit()
ans=-10**18
for i in range(n):
  ans=max(ans,s-2*b[i])
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    res = 0
    cnt = 0
    m = 10**10
    for i in a:
        if i < 0:
            cnt += 1
        res += abs(i)
        m = min(m, abs(i))
    if cnt%2==1:
        print(res-m*2)
    else:
        print(res)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

minus_num=len([el for el in A if el<0])
#print(minus_num)
new=[abs(el) for el in A]
#print(new)
if minus_num%2==1:
    #print('a')
    #print(sum(new))
    #print(min(new), sum(new))
    print(sum(new)-min(new)*2)
else:
    print(sum(new))

Submission status: Accepted

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

a = bisect.bisect(lis, 0)
su = 0
mi = 10**10

for b in lis:
    su += abs(b)
    mi = min(mi, abs(b))

if a % 2 == 0:
    print(su)
else:
    print(su - 2 * mi)

Submission status: Accepted

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

min_v = 10**9+1
cnt_min = 0
res = 0
for i, a in enumerate(A_list):
    if a < 0:
        cnt_min += 1
        a = -1 * a
    min_v = min(min_v, a)
    res += a

if cnt_min%2 == 1:
    res -= 2*min_v
print(res)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())
zero = 0
minus = 0
for i in a:
        if i==0: zero += 1
        if i<0: minus += 1
b = [abs(i)for i in a]

if minus%2==0 or zero>0: print(sum(b))
else: print(sum(b)-min(b)*2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

    abs_min = float('inf')
    minus_cnt = 0
    for e in a:
        if e < 0:
            minus_cnt += 1
        if abs(e) < abs_min:
            abs_min = abs(e)

    s = sum([abs(e) for e in a])
    if minus_cnt % 2:
        print(s - 2 * abs_min)
    else:
        print(s)
            

submit()

Submission status: Accepted

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

count=0
m=abs(A[0])
SUM=0
for a in A:
  if a<0:
    count+=1
  m=min(m, abs(a))
  SUM+=abs(a)

if count%2==0:
  print(SUM)
else:
  print(SUM-2*m)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=0
is_zero=False

for aa in a:
    if aa<0:c+=1
    if aa==0:is_zero=True

a=[abs(aa) for aa in a]
if c%2==0 or is_zero==True:
    print(sum(a))
else:
    print(sum(a)-2*min(a))

Submission status: Accepted

Solution code:
def main():

    n = int(input())
    a = list(map(int,input().split()))
    cnt_mns = 0
    mini = 10000000000
    sm = 0
    for i, aa in enumerate(a):
        if aa < 0:
            cnt_mns += 1

        if abs(aa) < mini:
            mini = abs(aa)
        sm += abs(aa)
    if cnt_mns % 2 == 1:
        print(sm - 2 * mini)
        
    else:
        print(sm)




if __name__ == '__main__':


    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
c = 0
m = -10**9 + 7
p = 10**9 + 7
s = 0
for e in A:
    s += abs(e)
    if e < 0:
        m = max(m,e)
        c += 1
    else:
        p = min(p,e)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
count=0
sum=0
A=float("inf")
for i in L:
	sum+=abs(i)
	A=min(A,abs(i))
	if i<0:
		count+=1
if count%2==0:
	print(sum)
else:
	B=float("inf")
	for i in L:
		if abs(i)==A:
			if i==0:
				print(sum)
				exit()
			elif i>0:
				print(sum-2*i)
				exit()
			elif i<0:
				print(sum-2*A)
				exit()

Submission status: Accepted

Solution code:
N = int(input())
A = []
count_natural = 0
count_minus = 0
min = 10000000000
for p in map(int, input().split()):
  if p > 0:
    count_natural += 1
  else:
    count_minus += 1
  min = abs(p) if abs(p) < min else min
  A.append(abs(p))
if count_minus % 2 == 0:
  print(sum(A))
else:
  print(sum(A) - min * 2)

Submission status: Accepted

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

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

C = [abs(a) for a in A]
C.sort(reverse=True)
if cnt%2 == 0:
    print(sum(C))
else:
    C[-1] *= (-1)
    print(sum(C))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
minus_cnt = 0
for i in range(len(A)):
    if A[i] < 0:
        minus_cnt += 1
        A[i] = -A[i]
if minus_cnt % 2 == 0:
    print(sum(A))
else:
    tmp = float("inf")
    for a in A:
        if tmp > abs(a):
            tmp = a
    print(sum(A) - 2 * tmp)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
m = 10 ** 9 #絶対値の最小
c = 0 #マイナスの数
for i in range(N):
  ans += abs(A[i])
  if m > abs(A[i]):
    m = abs(A[i])
  if A[i] < 0: c += 1
print(ans if c % 2 == 0 else ans - 2 * m)

Submission status: Accepted

Solution code:
# Problem D - Flipping Signs

# input
N = int(input())
a_list = list(map(int, input().split()))

# initialization
minus_count = 0
max_cost = 0

# count
for a in a_list:
    if a<0:
        minus_count += 1

# check
if minus_count%2==0:
    for a in a_list:
        max_cost += abs(a)
    print(max_cost)
else:
    min_abs = 10**10
    for a in a_list:
        min_abs = min(min_abs, abs(a))
        max_cost += abs(a)
    print(max_cost - min_abs*2)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

x = [0] * N
c = 0

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

ans = sum(x)
if c % 2 == 1:
    ans -= min(x) * 2

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    _ = int(input())
    A = [int(i) for i in input().split()]
    sumA = sum(abs(a) for a in A)
    mi = len([a for a in A if a < 0])
    if 0 in A or mi % 2 == 0:
        print(sumA)
    else:
        print(sumA - 2*min(abs(a) for a in A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

abs_sum = 0
minus = 0
abs_list = []
for i in range(n):
    if A[i] < 0:
        minus += 1
    abs_list.append(abs(A[i]))
    abs_sum += abs_list[i]

if minus % 2 != 0:
    abs_sum -= min(abs_list)*2
print(abs_sum)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
abs_min=10**10
abs_sum=0
neg_cnt=0
for a in A:
    if a<0:
        neg_cnt+=1
        a=-a
    abs_min = min(abs_min, a)
    abs_sum+=a
if neg_cnt&1==0:
    print(abs_sum)
else:
    print(abs_sum-abs_min-abs_min)

Submission status: Accepted

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

s = 0
for i in range(N):
    s += abs(A[i])

if 0 in A:
    print(s)
    exit(0)

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

if parity % 2 == 0:
    print(s)
    exit(0)

mx = 1 << 30
for i in range(N):
    mx = min(mx , abs(A[i]))
print(s - mx * 2)

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
ans = 0
if cnt % 2 == 0:
    for i in range(n):
        ans += abs(a[i])
    print(ans)
else:
    tar = abs(a[0])
    for i in range(n):
        ans += abs(a[i])
        if tar > abs(a[i]):
            tar = abs(a[i])
    print(ans-2*tar)

Submission status: Accepted

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

minus = sum([a < 0 for a in A])
ans = sum(B)

if minus % 2 == 1:
    ans -= min(B) * 2

print(ans)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    DP = [[-10 ** 20] * 2 for _ in range(N)]
    DP[0][0] = A[0]
    DP[0][1] = -1 * A[0]
    for i in range(1, N):
        a = A[i]
        DP[i][0] = max(max(DP[i-1][0] + a, DP[i-1][1] - a), DP[i][0])
        DP[i][1] = max(max(DP[i-1][0] - a, DP[i-1][1] + a), DP[i][1])

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(input().split(), dtype=np.int64)

neg = np.count_nonzero(A[A < 0])
ans = np.abs(A).sum()
if neg % 2 == 1:
    v = np.abs(A).min()
    ans -= 2 * v

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(map(int, input().split()))
ct0 = 0
ct1 = 0
ans = 0
for i in range(n):
    if a[i] < 0:
        ct1 += 1
    elif a[i] == 0:
        ct0 += 1

for i in range(n):
    ans += abs(a[i])
        
if ct0 > 0 or ct1 % 2 == 0:
    print(ans)
elif ct1 == n:
    print(ans+2*a[ct1-1])
else:
    print(ans-2*min(-a[ct1-1], a[ct1]))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
ans = sum(np.abs(A))
if np.count_nonzero(A < 0) %2 !=0:
    ans -= min(np.abs(A))*2
print(ans)

Submission status: Accepted

Solution code:
x=int(input())
y=list(map(int, input().split()))
t=1
for i in range(x):
	if y[i]<0:
		t=t*-1
	y[i]=abs(y[i])

if t==1:
	print(sum(y))
else:
	print(sum(y)-(min(y)*2))

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 -= 1000000000000
        break
    elif a[i] < 0:
        cnt += 1
a = [abs(a[i]) for i in range(n)]
if cnt < 0 or cnt % 2 == 0:
    print(sum(a))
else:
    print(sum(a) - 2*min(a))

Submission status: Accepted

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

negative = 0
mi = 10 ** 9 + 1
zero = False
ans = 0
for ai in a:
    if ai < 0:
        negative += 1
    if abs(ai) < mi:
        mi = abs(ai)
    ans += abs(ai)
if negative % 2:
    ans -= 2 * mi
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A =list(map(int,input().split()))
num = 0
for i in range(N):
    if A[i] == 0:
       num = - float('inf')
       break
    elif A[i] < 0:
        num += 1

A = [abs(A[i]) for i in range(N)]
if num < 0 or num % 2  == 0:
    print(sum(A))

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

Submission status: Accepted

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

cnt = 0
ans = 0
m = float("INF")
for i in range(N):
  if A[i] < 0:
    cnt += 1
  m = min(m, abs(A[i]))
  ans += abs(A[i])

if cnt % 2 == 1:
  ans -= 2 * m

print(ans)

Submission status: Accepted

Solution code:
import copy
import math
import string
import heapq
import bisect
import sys
sys.setrecursionlimit(10**7)

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

Submission status: Accepted

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

Submission status: Accepted

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

a_abs = [abs(a[i]) for i in range(n)]
a_abs_sum = sum(a_abs)

# aに0が含まれれば、全部正となるようフリップできる
if 0 in a:
    print(a_abs_sum)
else:
    # 0を含まず、かつ負の数が偶数ならば、同様にすべて正にフリップできる
    even = len([1 for i in range(n) if a[i] < 0])
    if even % 2 == 0:
        print(a_abs_sum)
    else: # 上記以外の場合は、絶対値のもっとも小さいものに負を寄せる
        print(a_abs_sum - 2*min(a_abs))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=0
zero=0
ans=0
mn=1000000001
for x in a:
  mn=min(mn,abs(x))
  if x<0:
    cnt+=1
    ans-=x
  else:
    ans+=x
  #print(ans)
cnt%=2
if cnt==0:
  print(ans)
else:
  print(ans-mn*2)
  
  
  
  
  
#print(ans,cnt,mn)

Submission status: Accepted

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

Submission status: Accepted

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

cnt = 0
has_zero = False

for item in a_list:
    if item < 0:
        cnt += 1
    elif item == 0:
        has_zero = True

abs_list = list(map(abs, a_list))
abs_list.sort()

if has_zero:
    print(sum(abs_list))
elif cnt % 2 == 0:
    print(sum(abs_list))
else:
    print(sum(abs_list) - 2 * abs_list[0])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int,input().split()))
# sum(|a|)がmaxでこれを実現できないケースは負の数が連続で奇数個並んでいる箇所がある時
# その時は両端とその隣の正の数の４つの中で絶対値がminのものを負にするとOK
# 例外は負の数が連続で奇数個並んでいる箇所が１つ間に正を挟んで並んでいる時
# この考えだと簡単に言い換えできない。解説をみるとtotalの負の数が偶数なら全部せいにできる
s = sum([abs(i) for i in a])
if len([i for i in a if i < 0]) % 2 == 0:
  print(s)
else:
  print(s-2*min([abs(i) for i in a]))

Submission status: Accepted

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

if c % 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()))
m = 100000000000
count = 0
ans = 0
for i in range(n):
    if a[i] < 0:
        count += 1
    x = abs(a[i]) 
    ans += x
    m = min(m,x)
if count % 2 != 0:
    ans -= 2*m
print(ans)

Submission status: Accepted

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

mini = float("inf")

cnt = 0

for i in range(n):
    mini = min(mini,abs(a[i]))
    if a[i] < 0:
        cnt+=1
    a[i] = abs(a[i])

if cnt % 2 == 1:
    print(sum(a) - mini * 2)
else:
    print(sum(a))

Submission status: Accepted

Solution code:
#abc125d
n=int(raw_input())
a=map(int,raw_input().split())
suma=0
mina=10**5+1
minuscnt=0
for i in range(n):
 suma+=abs(a[i])
 mina=min(mina,abs(a[i]))
 if a[i]<0:
  minuscnt+=1
if minuscnt%2:
 print suma-2*mina
else:
 print suma

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    A=list(map(int,readline().split()))

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

    S=S if minus_count%2==0 else S-2*min_number
    print(S)
    
if __name__=="__main__":
    main()

Submission status: Accepted

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

def main():
    absA = [abs(a) for a in A]
    total = sum(absA)
    if 0 in A or not len([a for a in A if a < 0]) % 2:
        print(total) 
    else:
        print(total - 2*min(absA))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int, input().split()))
count = 0
gokei = 0
mi = float('inf')
flg = False
for i in arr:
    gokei += abs(i)
    mi = min(mi,abs(i))
    if i < 0:
        count += 1
    if i == 0:
        flg = True
if flg or count % 2 == 0:
    print(gokei)
else:
    print(gokei-mi*2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]

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

B = [abs(a) for a in A]
B.sort()
if fn%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()))
m = 0
for i in range(N):
    if A[i] < 0:
        m += 1
Ap = list(map(abs,A))
Ap.sort()
if m %2 == 1:
    ans = sum(Ap) - 2*Ap[0]
else:
    ans = sum(Ap)
print(ans)

Submission status: Accepted

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

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

apos = []
aneg = []

for a in A:
    if a >=0: apos.append(a)
    else: aneg.append(a)

apos.sort()
aneg.sort()

if len(aneg) % 2 == 0:
    ans = sum(apos) - sum(aneg)
else:
    if len(apos) == 0:
        ans = - sum(aneg) + 2*aneg[-1]
    else:
        if abs(apos[0]) > abs(aneg[-1]):
            ans = sum(apos) - sum(aneg) -  2*abs(aneg[-1])
        else:
            ans = sum(apos) - sum(aneg) - 2*abs(apos[0])


print(ans)

Submission status: Accepted

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

min = 10**9
minus = 0
for i in range(len(A)):
    if A[i] < 0:
        minus += 1
    if abs(A[i]) < min:
        min = abs(A[i])
    A[i] = abs(A[i])

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

Submission status: Accepted

Solution code:
N = int(input())

A = sorted(list(map(int, input().split())))
'''
INF = 10**6

ind = INF
for i in range(len(A)):
    if A[i]>=0:
        ind = i
        break
    else:
        A[i] *= -1

if ind == INF:
    ind = N

if ind %2 == 0:
    print(sum(A))
elif ind==N:
    print(sum(A)-2*A[ind-1])
else:
    print(sum(A)-2*min(A[ind], A[ind-1]))
'''
start = 0
end = N-1

while end != start:
    if A[(start+end)//2] >= 0:
        end = (start+end)//2
    elif end-start==1:
        start = (start+end)//2+1
    else:
        start = (start+end)//2

if start==N-1 and A[N-1]<0:
    start=N

if start%2==0:
    print(sum(A[:start])*(-1) + sum(A[start:]))
elif start==N:
    print(sum(A[:start])*(-1) + sum(A[start:]) + 2*A[N-1])
else:
    print(sum(A[:start])*(-1) + sum(A[start:]) - 2*min(A[start], (-1)*A[start-1]))