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: Time Limit Exceeded

Solution code:
n=int(input())
aa=list(map(int,input().split()))
aa.append(0)
aaa=tuple(aa)
a=list(aaa)
x=[0]*(n+1)
for i in range(n-1):
    if a[i]<0:
        a[i]=-1*a[i]
        a[i+1]=-1*a[i+1]
        x[i+1]=max(sum(a),x[i])
b=list(aaa)
y=[0]*(n+1)
for i in range(n,0,-1):
    if b[i]<0:
        b[i]=-1*b[i]
        b[i-1]=-1*b[i-1]
        y[i+1]=max(sum(b),y[i])

print(max(max(x),max(y),sum(aa)))

Submission status: Time Limit Exceeded

Solution code:
# D

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

# abs_list = sorted([abs(x) for x in A])[::-1]

for i in range(N-1):
    if A[i] < 0:
        A[i] *= -1
        A[i+1] *= -1
    
tmp = [sum(A)]
for i in reversed(range(0, N-1)):
    A[i] *= -1
    A[i+1] *= -1
    tmp.append(sum(A))
    
print(max(tmp))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
abs_a = []
minus = 0

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

if minus % 2 == 0:
  for i in range(n):
    abs_a.append(abs(a[i]))
  print(sum(abs_a))
else:
  for i in range(n):
    abs_a.append(abs(a[i]))
    min_abs_a = min(abs_a)
  print(sum(abs_a)-min_abs_a*2)

Submission status: Time Limit Exceeded

Solution code:
raw_input()
data = [int(i) for i in raw_input().split()]

prev = None

while True:
    cur = sum(data)

    min1 = min(data)
    min1_ind = data.index(min1)
    data.pop(min1_ind)
    min2 = min(data)
    min2_ind = data.index(min2)
    data.pop(min2_ind)

    if prev is not None and prev >= cur:
        break

    data += [-min1, -min2]
    prev = cur

print(prev)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
columns = list(map(int, input().split(' ')))
columns2 = sorted(columns, reverse = True)

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


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

result1,result2 = 0, 0
for x in columns:
    result1 += x
for y in columns2:
    result2 += y

if result1 > result2:    
    print(result1) 
else:
    print(result2)

Submission status: Time Limit Exceeded

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

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

# 正の数p, 負の数nに対して、p+n=N
# 全探索は2^Nで爆発

while True:
    ch = False
    for i in range(0, N-1):
        if i < N-2 and 2*A[i]+3*A[i+1]+2*A[i+2] < 0:
            A[i] *= -1
            A[i+2] *= -1
            ch = True
        if A[i] + A[i+1] < 0:
            A[i] *= -1
            A[i+1] *= -1
            ch = True
    if ch is False:
        break

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
raw_input()
data = [int(i) for i in raw_input().split()]

prev = None

while True:
    data = sorted(data)

    cur = sum(data)
    if prev is not None and prev >= cur:
        break

    data[0] = -data[0]
    data[1] = -data[1]
    prev = cur

print(prev)

Submission status: Time Limit Exceeded

Solution code:
raw_input()
data = [int(i) for i in raw_input().split()]

prev = None

while True:
    data = sorted(data)

    cur = sum(data)
    if prev is not None and prev > cur:
        break

    data[0] = -data[0]
    data[1] = -data[1]
    prev = cur

print(prev)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
columns = list(map(int, input().split(' ')))
columns2 = sorted(columns, reverse = True)

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


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

result1,result2 = 0, 0
for x in columns:
    result1 += x
for y in columns2:
    result2 += y

if result1 > result2:    
    print(result1) 
else:
    print(result2)

Submission status: Time Limit Exceeded

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

ans = sum(A)
for i in range(N):
  if A[i] < 0:
    if i != N-1:
      A[i] = A[i] * -1
      A[i+1] = A[i+1] * -1
  ans = max(ans, sum(A))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
raw_input()
data = [int(i) for i in raw_input().split()]

while True:
    data = sorted(data)
    if data[0] + data[1] <= 0:
        data[0] = -data[0]
        data[1] = -data[1]
    else:
        break

print(sum(data))

Submission status: Time Limit Exceeded

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

while True:
	updated = False
	for i in range(N-1):
		for j in range(i+1, N):
			if (A[i] + A[j] < 0):
				updated = True
				A[i] *= -1
				A[j] *= -1
				updated = True
	if not updated:
		break

print(sum(A))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Accepted

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

if minus % 2 == 1:
    ans = sum(abs_ls) - 2 * min(abs_ls)
else:
    ans = sum(abs_ls)
print(ans)

Submission status: Accepted

Solution code:
N = int(input()); INF = float("inf")
A = list(map(int,input().split()))
#dp[i+1][j]: i番目まで見てj=0(i番目がそのまま),j=1(i番目が逆転)の時の最大値
dp = [[-INF]*2 for _ in range(N)]
dp[0][0] = 0
dp[0][1] = 0
dp[1][0] = A[0]+A[1]
dp[1][1] = -(A[0]+A[1])
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(dp)
ans = max(dp[N-1])
print(ans)

Submission status: Accepted

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

plus=0
zero=0
minus=0

for i in range(N):
    if A[i]>0:
        plus+=1
    elif A[i]<0:
        minus+=1
    else:
        zero+=1
ans=0
m=10**9+10
for i in range(N):
    ans+=abs(A[i])
    m=min(m,abs(A[i]))


if minus%2==0 or zero>0:
    pass
else:
    
    ans=ans-2*m

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
list_A = list(map(int, input().split()))
m = pow(10, 10)
s = 0
cnt = 1

for a in list_A:
    m = min(m, abs(a))
    if a < 0:
        cnt *= -1
    s += abs(a)

if cnt == 1:
    print(s)
else:
    print(s - 2 * m)

Submission status: Accepted

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

Submission status: Accepted

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

def main(n,a):
    init = sum(a)
    dp = [init,init-2*a[0]-2*a[1]]
    #print(dp)
    for i in range(1,n-1):
        prev1 = dp[0]
        prev2 = dp[1]
        dp[0] = max(prev1,prev2)
        dp[1] = max(prev2+2*a[i]-2*a[i+1],prev1-2*a[i]-2*a[i+1])
        #print(dp)
    print(max(dp))

if __name__=="__main__":
    n,a = getval()
    main(n,a)

Submission status: Accepted

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

souwa = 0
cnt = 0
keep = 1e10

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

    souwa += A[i]
    keep = min(keep, A[i])

print(souwa - 2 * keep * (cnt % 2))

Submission status: Accepted

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

dp = [[0]*2 for _ in range(n)]
# dp[i][0]:*1
# dp[i][1]:*(-1)
for i in range(n-1):
    if i == 0:
        dp[i+1][0] += A[i]
        dp[i+1][1] += -A[i]
    else:
        dp[i+1][0] = max(dp[i][0]+A[i], dp[i][1]+(-1)*A[i])
        dp[i+1][1] = max(dp[i][0]+(-1)*A[i], dp[i][1]+A[i])
ans = max(dp[n-1][0]+A[n-1], dp[n-1][1]+(-1)*A[n-1])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
A = np.array(list(map(int,input().split())))
minus = np.count_nonzero(A < 0)
A = np.abs(A)

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

Submission status: Accepted

Solution code:
import numpy as np

n=int(input())
A=np.array(list(map(int,input().split())))
minus = np.count_nonzero(A < 0)
A = np.abs(A)

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

Submission status: Accepted

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

A.sort(reverse=True)
if zero==True:
    print(sum(A))
else:
    if minus==0:
        print(sum(A))
    else:
        print(sum(A[0:N-1])-A[-1])

Submission status: Accepted

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
cnt = 0
zero = False
for a in A:
    if a < 0:
        cnt += 1
    elif a == 0:
        zero = True

if cnt%2 == 0 or zero:
    print(sum(map(abs, A)))
else:
    A = sorted(map(abs, A))
    print(sum(A) - 2*A[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math


def main():
    n = int(input())
    # a, b, t = map(int, input().split())
    # h = list(map(int, input().split()))
    # s = input()
    # h = [int(input()) for _ in rane(n)]

    a = list(map(int, input().split()))
    abs_a = []
    minus = 0
    for ai in a:
        if ai < 0:
            minus += 1
        abs_a.append(abs(ai))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
A = rl()

num_min = len([a for a in A if a < 0])
B = [abs(a) for a in A]
if num_min % 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()))
ans = 0
cnt_minus = 0
cnt_zero = 0
m = 10**9
for i in a:
    ans += abs(i)
    if i<0:
        cnt_minus += 1
    if i==0:
        cnt_zero +=1
    m = min(m,abs(i))

if cnt_minus % 2 == 0 or cnt_zero !=0:
    print(ans)
else:
    print(ans-2*m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():






    n = I()
    a = LI()

    ans = 0
    mn = 0

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

    if (mn %2 == 0):
        ans = sum(a)
    else:
        ans = sum(a)-min(a)*2

    print(ans)

                    


main()

Submission status: Accepted

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

a.sort()
abs_a = [abs(x) for x in a]
minus = []

for x in a:
    if x < 0:
        minus.append(x)

tmp = sum(abs_a)

if len(minus) % 2 == 0:
    print(tmp)
else:
    print(tmp - min(abs_a)*2)

Submission status: Accepted

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

a.sort()
minus, plus = [], []

for x in a:
    if x < 0:
        minus.append(x)
    else:
        plus.append(x)

tmp = sum([abs(x) for x in a])

if len(minus) % 2 == 0:
    print(tmp)
else:
    if plus == [] or abs(minus[-1]) < plus[0]:
        print(tmp + minus[-1] * 2)
    else:
        print(tmp - plus[0] * 2)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
Amin = 10 ** 9 + 1
flag = 0
for i in range(N):
  if i < N-1 and A[i] < 0:
    A[i] = -A[i]
    A[i+1] = -A[i+1]
  elif i == N-1 and A[i] < 0:
    A[i] = -A[i]
    flag = -1
    
  ans += A[i]
  
  if A[i] < Amin:
    Amin = A[i]
    
print(ans + (flag * 2 * Amin))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
x=0
b=[]
for i in a:
  if i<0: x=x+1
  b.append(abs(i))
b.sort()
print(sum(b)-b[0]*2 if  x%2 else sum(b))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    abs_a = list(map(abs, a))

    cnt = 0
    for i in a:
        if i < 0:
            cnt += 1
        elif i == 0:
            print(sum(abs_a))
            exit()

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

main()

Submission status: Accepted

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

# マイナスの数が偶数ならば、絶対値を取って和を出力する。
# マイナスの数が奇数ならば、絶対値を取った和から絶対値が一番小さいもの*2を引く。
abs_min = 10**9
flag = False
if A.count(0) >= 1:
  flag = True
neg_count = 0
ans = 0
for a in A:
  ans += abs(a)
  if a < 0:
    neg_count += 1
  if abs(a) < abs_min:
      abs_min = abs(a)
if neg_count %2 == 0:
  flag = True

if flag:
  print(ans)
else:
  print(ans - 2 * abs_min)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = len([x for x in a if x < 0])
a = list(map(abs, a))
a.sort()
print(sum(a) if m % 2 == 0 else sum(a[1:])-a[0])

Submission status: Accepted

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

s = [abs(i) for i in a]
minus = sum([1 for i in a if i < 0])
print(sum(s) if minus%2 == 0 else sum(s)-2*min(s))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
c = 0
s = 0
ma = 10**6
for i in a:
    if i<0:
        c+=1
        c%=2
    s += abs(i)
    ma = min(ma,abs(i))
if c == 1:
    print(s-2*ma)
else:
    print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(abs,A))
print(sum(B)-2*min(B)*(sum(a<0 for a in A)%2))

Submission status: Accepted

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

Submission status: Accepted

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

if 0 in A:
    ans = sum(map(abs, A))
    print(ans)
    exit()
else:
    negs = 0
    for a in A:
        if a < 0:
            negs += 1

    if negs % 2 == 1:
        A = list(map(abs, A))
        A.sort()
        # print(A, sum(A))
        ans = sum(A) - 2 *A[0]
        print(ans)
    else:
        ans = sum(map(abs, A))
        print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N,A=ilint()
B=[abs(a) for a in A]
if sum([a<0 for a in A])%2==0:
    print(sum(B))
else:
    print(sum(B)-2*min(B))

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n = i_input()
    a = i_list()
    m = INF
    l = []
    cnt = 0
    for i in a:
        if i < 0:
            cnt += 1
        i = abs(i)
        l.append(i)
        m = min(m,i)

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



if __name__=="__main__":
    main()

Submission status: Accepted

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

cnt = len([i for i in A if i < 0])
PA = list(map(abs, A))

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=0
for i in a:
  if i<0:
    c^=1

a=list(map(abs,a))
a.sort()
if c:
  print(sum(a)-a[0]*2)
else:
  print(sum(a))

Submission status: Accepted

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

m = 0

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

if m % 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()))
c = 0
for i in range(n):
    if a[i] < 0:
        c += 1
        a[i] = abs(a[i])
if c % 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()))
num_minus = sum([1 if v < 0 else 0 for v in A])
sum_abs = sum([abs(v) for v in A])
min_abs = min([abs(v) for v in A])
print(sum_abs if num_minus % 2 == 0 else sum_abs - min_abs * 2)

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
import numpy as np
# import heapq
# from collections import deque

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

B = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

num_minus = len(B[B < 0])
abs_tot = sum(list(map(abs, A)))
if num_minus % 2 == 0:
    print(abs_tot)
else:
    n_0 = 10**9
    for i in A:
        a = abs(i)
        if a < n_0:
            n_0 = a
    print(abs_tot - (n_0 * 2))

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
from functools import lru_cache
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]

@lru_cache(maxsize=None)
def dp(i, j):
    if i == 0:
        return 0 if j == 0 else -INF
    if j == 0:
        return max(dp(i - 1, 0) + a[i-1], dp(i - 1, 1) - a[i-1])
    else:
        return max(dp(i - 1, 0) - a[i - 1], dp(i - 1, 1) + a[i - 1])


n = I()
a = LI()


def main():
    print(dp(n, 0))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
# import numpy as np
import sys
from functools import lru_cache
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]

@lru_cache(maxsize=None)
def dp(i, j):
    if i == 0:
        return 0 if j == 0 else -INF
    if j == 0:
        return max(dp(i - 1, 0) + a[i-1], dp(i - 1, 1) - a[i-1])
    else:
        return max(dp(i - 1, 0) - a[i - 1], dp(i - 1, 1) + a[i - 1])


n = I()
a = LI()
print(dp(n, 0))

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import numpy as np
import sys
from functools import lru_cache
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


@lru_cache(maxsize=None)
def dp(i, j):
    if i == 0:
        return 0 if j == 0 else -INF
    if j == 0:
        return max(dp(i - 1, 0) + a[i-1], dp(i - 1, 1) - a[i-1])
    else:
        return max(dp(i - 1, 0) - a[i - 1], dp(i - 1, 1) + a[i - 1])


n = I()
a = LI()


def main():
    print(dp(n, 0))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	A = [int(a) for a in input().split(" ")]
	if A.count(0) > 0:
		print(sum([abs(a) for a in A]))
		return 0
	minus = 0
	for i in range(len(A)):
		if A[i] < 0:
			minus += 1
	if minus % 2 == 0:
		print(sum([abs(a) for a in A]))
		return 0
	A.sort(key=lambda a: abs(a))
	print(sum([abs(a) for a in A[1:]]) - abs(A[0]))

main()

Submission status: Accepted

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

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

abs_a = list(map(abs,a))
if minus_num % 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()))

law_ans = 0
absminA = float('inf')
for a in A:
    law_ans += abs(a)
    absminA = min(absminA, abs(a))


cnt_neg = 0

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

cnt_0 = A.count(0)

if cnt_neg%2 == 0:
    print(law_ans)
else:
#０があるときはいつでもlaw_ansになるが、absminAが0だからおっけい
    print(law_ans-2*absminA)

Submission status: Accepted

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

law_ans = 0
absminA = float('inf')
for a in A:
    law_ans += abs(a)
    absminA = min(absminA, abs(a))


cnt_neg = 0

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

cnt_0 = A.count(0)

if cnt_neg%2 == 0:
    print(law_ans)
else:
    print(law_ans-2*absminA)

Submission status: Accepted

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

law_ans = 0
absminA = float('inf')
for a in A:
    law_ans += abs(a)
    absminA = min(absminA, abs(a))


cnt_neg = 0

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

cnt_0 = A.count(0)

if cnt_0 == 0:
    if cnt_neg%2 == 0:
        print(law_ans)
    else:
        print(law_ans-2*absminA)
else:
    print(law_ans)

Submission status: Accepted

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

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

abs_A = list(map(abs, A))
sum_ = sum(abs_A)

if minus_cnt % 2 == 0:
    ans = sum_
else:
    ans = sum_ - 2*min(abs_A)

print(ans)

Submission status: Accepted

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

# dp[i][j]：A_1,...,A_iを確定させ, A_iの符号をj回反転させたときの
# Aの和の最大値

INF = float('inf')
dp = [[-INF]*2 for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(2):
        dp[i+1][j] = max(dp[i][0]+A[i]*(-1)**j, dp[i][1]-A[i]*(-1)**j)
print(dp[N][0])

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[abs(x) for x in A]
ct=0
for i in range(N):
  if A[i]!=B[i]:
    ct+=1
B.sort()
if B[0]==0 or ct%2==0:
  print(sum(B))
else:
  B[0]*=(-1)
  print(sum(B))

Submission status: Accepted

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

#負の数カウントと絶対値リスト作成
abs_As = []
negative_count = 0

for A in As:
    if(A <= 0):
        abs_As.append(abs(A))
        negative_count += 1
    
    else:
        abs_As.append(A)

#print(As)
#print(abs_As)
#print(negative_count)

if(negative_count % 2 == 0):
    print(sum(abs_As))

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