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 functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    A = list(int(_) for _ in input().split())
    min_cnt = 0
    for i in range(N):
        if A[i] < 0:
            min_cnt +=1
        A[i] = abs(A[i])
    if min_cnt % 2 ==0:
        ans = sum(A)
    else:
        ans = sum(A)-2*(min(A))
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

A_m = list()
A_p = list()
for a in A:
    if a >= 0: A_p.append(a)
    else: A_m.append(a)
M = 0
M += sum(A_p)
M -= sum(A_m)
if len(A_m)%2:
    A_abs = list(map(abs, A))
    M = sum(A_abs)
    M -= 2*min(A_abs)
print(M)

Submission status: Accepted

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

f = False
n = 0

for i in range(N):
    if A[i] == 0:
        f = True
    elif A[i] < 0:
        n += 1
        A[i] = abs(A[i])

ans = 0
for i in A:
    ans += i

if f:
    print(ans)
elif n % 2 == 0:
    print(ans)
elif n % 2 == 1:
    print(ans - 2 * min(A))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
S = 0
temp = 0
flg = False

for i in A:
    S += abs(i)
    if i < 0:
        temp += 1
    if i == 0:
        flg = True

if temp % 2 == 0 or flg is True:
    print(S)
else:
    print(S - 2*min([abs(y) for y in A]))

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    total = 0
    mn = float('inf')
    cnt = 0
    for a in A:
        if a < 0:
            cnt += 1
        mn = min(mn, abs(a))
        total += abs(a)
    if cnt % 2 != 0:
        total -= mn * 2
    print(total)
    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())
A = list(map(int, input().split()))

count = 0
flag = False
l = [abs(i) for i in A]
if 0 in A:
  pass
else:
  for j in A:
    if j < 0:
      count += 1
  if count % 2 == 0:
    pass
  else:
    flag = True
    
if flag:
  print(sum(l)-min(l)*2)
else:
  print(sum(l))

Submission status: Accepted

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

minus_cnt = 0
abs_min = float('inf')
abs_sum = 0
for ai in a:
    if ai<0:
        minus_cnt += 1
    abs_min = min(abs_min, abs(ai))
    abs_sum += abs(ai)

if minus_cnt%2==0:
    print(abs_sum)
else:
    print(abs_sum - 2*abs_min)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
# A, B, T = map(int, input().split())
# S = input()

dp = [[0, 0] for _ in range(N)]

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

Submission status: Accepted

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

abs_sum = sum(abs(a) for a in A)
if sum(a < 0 for a in A) %2 == 0:
    print(abs_sum)
    exit(0)
abs_min = min(abs(a) for a in A)

print(abs_sum - 2*abs_min)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
dp = [[0, 0] for _ in range(N-1)]
dp[0][0] = A[0] + A[1]
dp[0][1] = -dp[0][0]

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
num = list(map(int,input().split()))
c=0
ans=0
for i in range(N):
  if num[i]<0:
    c+=1 
ans = list(map(lambda x: abs(x),num))
if c%2==0:
  print(sum(ans))
else:
  print(sum(ans) - min(ans,key=lambda x: abs(x))*2)

Submission status: Accepted

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
N = ni()
A = na()
minas=0
tmp=10**9
for i in range(N):
    tmp = min(tmp,abs(A[i]))
    if(A[i]<0):
        minas +=1
        A[i]=-A[i]

#負の数が奇数個
if(minas%2==1):
    #print(tmp)
    print(sum(A)-2*tmp)
else:
    print(sum(A))

Submission status: Accepted

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

Submission status: Accepted

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

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

cnt = 0
abs_A = []
for i in range(N):
    if A[i] < 0:
        cnt += 1
        abs_A.append(-A[i])
    else:
        abs_A.append(A[i])
ans = sum(abs_A)
if cnt % 2 != 0:
    ans -= 2*min(abs_A)

print(ans)

Submission status: Accepted

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

count = sum([a < 0 for a in A])
abss = [abs(a) for a in A]

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

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:
    neg += 1
    A[i] = -A[i]
tot = 0
for i in range(N):
  tot += A[i]
if neg % 2 == 0:
  print(tot)
else:
  print(tot - 2 * min(A))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
ans = 0
res = 0
flag = 0
for i in range(len(A)):
    if A[i]<0:
        res += 1
        A[i] *= -1
    elif A[i] == 0:
        flag = 1
if res%2 == 1 and flag != 1:
    print(sum(A) - min(A)*2)
else:
    print(sum(A))

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
s=0
for i in range(n):
    s+=abs(a[i])
if cnt%2==1:
    c=10**10
    for i in range(n):
        num=abs(a[i])
        if num<c:
            c=num
    s=s-(c*2)
print(s)

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	A= list(map(int, input().split()))
	pos = []
	neg = []
	ans = 0
	min_neg = 10**9
	min_pos = 10**9
	for i in range(N):
		if A[i] > 0:
			pos.append(A[i])
			min_pos = min(min_pos, A[i])
		else:
			neg.append(-A[i])
			min_neg = min(min_neg, -A[i])
	ans = sum(neg)+sum(pos)
	if len(neg)%2 == 1:
		ans -= 2*min(min_pos, min_neg) 
	print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

B = [0]*N
S = 0
cnt = 0
flag = False
for i in range(N):
    if A[i]>0:
        B[i] = A[i]
        S += B[i]
    elif A[i]<0:
        B[i] = -A[i]
        S += B[i]
        cnt += 1
    else:
        flag = True
if cnt%2==0 or flag:
    print(S)
else:
    print(S-2*min(B[i] for i in range(N)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np;
sys.stdin.readline()
a=np.array(sys.stdin.readline()[:-1].split(),dtype=np.int64)
b=np.abs(a)
print(np.sum(b)-((np.sum(np.sign(a)<0)%2)>0)*2*np.min(b))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))

dp = np.zeros((N+1, 2), dtype=int)
dp[0, 1] = -10**9

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().strip())
A = list(map(int, input().strip().split(' ')))
_A = [abs(a) for a in A]
if len([1 for a in A if a < 0]) % 2 == 0:
  print(sum(_A))
else:
  _A = sorted(_A)
  print(sum(_A[1:])-_A[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin

INF = 10 ** 16

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

"""
dp[i][j]を j=1 ならiを選んで反転した場合（すなわち A_i+1 の符号が反転している状態）
の A_1, A_2, ... , A_i の最大値として定義する

今反転しない & 前の状態（反転してない or 反転した）
今反転する & 前の状態（反転してない or 反転した）
といったような4状態から最大値をみつけていく感じ
"""
dp = [[None] * 2 for _ in range(N+10)]

dp[0][0] = 0
dp[0][1] = -INF # Invalid

for i in range(N):
    # A[i]を反転させない状態の最大値
    # dp[i][0]なら前の操作でA[i]は反転されていないのでそのまま足す
    # dp[i][1]なら前の操作でA[i]が反転されているので反転して足す
    dp[i+1][0] = max(dp[i][0]+A[i], dp[i][1]-A[i])

    # A[i]を反転させた状態の最大値
    # 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])


# for DEBUG
#print(*dp, sep="\n")

# Nは反転できないのでdp[N][0]が結果となる
print(dp[N][0])

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = A.copy()
B.sort()
C=[]
for i in range(N):
  if B[i]<0:
    C.append(B[i])
  else:
    continue
count = len(C)
if count % 2 == 0:
  B = np.abs(B)
  ans = sum(B)
else:
  B = np.abs(B)
  X = sum(B)
  ans = X - 2*min(B)
print(ans)

Submission status: Accepted

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

sc = 0
wmin = int(1e10)

for a in A:
  if a < 0:
    sc += 1
  wmin = min(wmin, abs(a))
  
ans = sum(B) if sc%2 == 0 else sum(B) - 2*wmin
print(ans)

Submission status: Accepted

Solution code:
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_

import sys
sys.setrecursionlimit(1000000)

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

rcd = dict()

# dynamic programming, dp(current_position, (i-1)-th_sign)
def dp(pos, sign):

    # boundary condition
    if pos == N-1:
        if sign == 0:
            return A[pos]
        else:
            return -A[pos]

    # if visit (pos, sign) state before
    if (pos, sign) in rcd:
        return rcd[(pos, sign)]

    elif sign == 0:
        # memorize
        rcd[(pos, sign)] = max( dp(pos+1, 0) + A[pos], dp(pos+1, 1) - A[pos])
        return rcd[(pos, sign)]

    else: # st == 1
        # memorize
        rcd[(pos, sign)] = max( dp(pos+1, 0) -  A[pos], dp(pos + 1, 1) + A[pos])
        return rcd[(pos, sign)]

print '{}'.format( dp(0,0) )

Submission status: Accepted

Solution code:
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_

import sys
sys.setrecursionlimit(1000000)

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

visit = dict()

def dp(pos, sign):
    # terminal condition
    if pos == N-1:
        if sign == 0:
            return A[pos]
        else:
            return -A[pos]

    if (pos, sign) in visit:
        return visit[(pos, sign)]

    elif sign == 0:
        # memorize
        visit[(pos, sign)] = max( dp(pos+1, 0) + A[pos], dp(pos+1, 1) - A[pos])
        return visit[(pos, sign)]

    else: # st == 1
        # memorize
        visit[(pos, sign)] = max( dp(pos+1, 0) -  A[pos], dp(pos + 1, 1) + A[pos])
        return visit[(pos, sign)]

print '{}'.format( dp(0,0) )

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

class Solution():
    def dp(self, pos, sign):
        if pos == self.n-1:
            if sign == 0:
                return +self.lst[pos]
            else:
                return -self.lst[pos]
        elif (pos, sign) in self.vis:
            return self.rcd[pos][sign]
        elif sign == 0:
            self.rcd[pos][sign] = max(self.dp(pos+1, 0) + self.lst[pos], self.dp(pos+1, 1) - self.lst[pos])
            self.vis.add((pos, sign))
            return self.rcd[pos][sign]
        else:
            self.rcd[pos][sign] = max(self.dp(pos+1, 0) - self.lst[pos], self.dp(pos+1, 1) + self.lst[pos])
            self.vis.add((pos, sign))
            return self.rcd[pos][sign]

    def run(self):
        self.n = int(input())
        self.lst = list(map(int, raw_input().split()))
        self.rcd = [[0, 0] for _ in range(self.n)]
        self.vis = set()
        print(self.dp(0, 0))

solution = Solution()
solution.run()

Submission status: Accepted

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

Submission status: Accepted

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

abs_total = 0
n_count = 0
min_abs_a = 10**9
for A in An:
    a = abs(A)
    abs_total += a
    if a < min_abs_a:
        min_abs_a = a
    if A <= 0:
        n_count += 1
if n_count%2 == 1:
    abs_total -= min_abs_a*2
print(abs_total)

Submission status: Accepted

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

flg = 1
ans = 0
mini = float("inf")
for a in A:
  if a < 0:
    flg *= -1
  elif a == 0:
    flg = 0
  ans += abs(a)
  mini = min(abs(a),mini)

if flg == -1:
  ans -= 2* mini
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))

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

a=np.array(a)
a=np.abs(a)
a=np.sort(a)
goukei=0

if mynas % 2 ==0:
    for j in range(n):
        goukei += a[j]
else:
    for k in range(n):
        goukei+=a[k]
    goukei-=a[0]*2

print(goukei)

Submission status: Accepted

Solution code:
#coding: utf-8
N = int(input())
A = list(map(int, input().split()))
dp = [[0, 0] for i in range(N+1)]
dp[0][1] = -10**10
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()))
new_a = []
sum = 0
minus_count = 0

for i in range(n):
	new_a.append(abs(a[i]))

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

if minus_count % 2 == 0:
	for i in range(n):
		sum += abs(a[i])
else:
	for i in range(n):
		sum += new_a[i]
	sum = sum - min(new_a) * 2

print(sum)

Submission status: Accepted

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

import sys
import copy

sys.setrecursionlimit(1000000)

# input = sys.stdin.readline

# ~~~~~~~~~~~~~~~~~~~~~_(＾～＾ ｣ ∠)_~~~~~~~~~~~~~~~~~~~~~

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

sumV = 0
for x in A:
    sumV += abs(x)

minus = sum(x < 0 for x in A)

if A.count(0) or minus % 2 == 0:
    print(sumV)
    exit()

minV = 1e15
for x in A:
    minV = min(minV, abs(x))

print(sumV - 2 * minV)

Submission status: Accepted

Solution code:
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_d

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

ng_cnt = 0

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

if ng_cnt % 2 == 0:
    print '{}'.format( sum(A) )
else:
    print '{}'.format( sum(A) - min(A)*2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding:utf-8


def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = []
    dp.append([0, -10**9-1])

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

    # print(dp)
    ans = dp[N][0]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(N, A):
    if len(list(filter(lambda x: x < 0, A))) % 2 == 0:
        return sum(map(abs, A))
    else:
        min_abs = min(map(abs, A))
        return sum(map(abs, A)) - 2 * min_abs


def solve_dp(N, A):
    """
    >>> N = 3
    >>> A = [-10, 5, -4]
    >>> solve_dp(N, A)
    19
    >>> N = 5
    >>> A = [10, -4, -8, -11, 3]
    >>> solve_dp(N, A)
    30
    """
    # 複数回同じインデックスを反転する意味はないので、各iについて反転回数は0, 1のいずれか
    # 考えられる結果の集合はN^2なので空間的には余裕
    # すべてのパターンをメモしながら動的計画法で解く

    # dp(i, j) = A_i-1までを確定とし、jによってA_iを反転させた場合のSUM(A_0 ~ A_i)の最大値
    dp = [[None, None] for _ in range(N)]
    for i in range(N - 1):
        if i == 0:
            dp[0][0] = A[0]
            dp[0][1] = -A[0]
            continue
        dp[i][0] = max(dp[i - 1][0] + A[i], dp[i - 1][1] - A[i])
        dp[i][1] = max(dp[i - 1][0] - A[i], dp[i - 1][1] + A[i])
    # i = N - 1の場合は反転操作は許されないので、可能なパターン2つを手作業で計算
    return max(dp[N - 2][0] + A[N - 1], dp[N - 2][1] - A[N - 1])


# import doctest
# doctest.testmod()

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

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
 
 
N = int(input())
An = list(map(int, sys.stdin.readline().rstrip().split()))
 
ans = 0
mn = 10**9
minus = 0
for a in An:
  mn = min(mn, abs(a))
  ans += abs(a)
  if a < 0:
    minus += 1
 
if minus%2 == 0:
  print(ans)
else:
  print(ans-mn*2)

Submission status: Accepted

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

def solveDp():
    POS, NEG = 0, 1
    dp = [[0 for _ in range(n + 1)] for _ in range(2)]
    dp[NEG][0] = -float('inf')
    for i in range(n):
        dp[POS][i + 1] = max(dp[POS][i] + a[i], dp[NEG][i] - a[i])
        dp[NEG][i + 1] = max(dp[POS][i] - a[i], dp[NEG][i] + a[i])
    print(dp[POS][n])

def solve():
    nNegative = 0
    total = 0
    minVal = float('inf')
    for num in a:
        if num < 0:
            num *= -1
            nNegative += 1
        minVal = min(minVal, num)
        total += num
    print(total if nNegative & 1 == 0 else total - 2 * minVal)

solveDp()

Submission status: Accepted

Solution code:
def solve(N, A):
    if len(list(filter(lambda x: x < 0, A))) % 2 == 0:
        return sum(map(abs, A))
    else:
        min_abs = min(map(abs, A))
        return sum(map(abs, A)) - 2 * min_abs


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

Submission status: Accepted

Solution code:
N = int(input())
aa = list(map(int, input().split()))
abs_sum = sum(map(abs, aa))
if 0 in aa:
    print(abs_sum)
    exit()
now = aa[-1]
for i in range(1, N):
    now = -aa[N-1-i] if now < 0 else aa[N-1-i]
if now < 0:
    print(abs_sum - 2 * min(map(abs, aa)))
else:
    print(abs_sum)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    cnt = 0
    minimum = float("inf")
    for i in range(N):
        ans += abs(A[i])
        minimum = min(minimum, abs(A[i]))
        if A[i] < 0:
            cnt += 1
    if cnt % 2 == 1:
        ans -= minimum * 2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

cnt = 0
min_val = abs(a[0])
for it in a:
    if abs(it) < min_val:
        min_val = abs(it)
    
    if it < 0:
        cnt+=1
        
abs_list = list(map(abs, a))
if cnt%2 == 0:
    print(sum(abs_list))
else:
    print(sum(abs_list) - 2*min_val)

Submission status: Accepted

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

sum = 0
m = 1e10  # 絶対値の最小値
negativeCount = 0
for i in range(N):
    sum += abs(A[i])
    m = min(m, abs(A[i]))
    if A[i] < 0:
        negativeCount += 1

if negativeCount % 2 == 1:
    sum -= m * 2

print(sum)

Submission status: Accepted

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

dp = [[0] * 2 for i in range(n)]
dp[0] = [a[0], -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])

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math


N = int(input())
An = list(map(int, sys.stdin.readline().rstrip().split()))

ans = 0
mn = 10**9
minus = 0
for a in An:
  mn = min(mn, abs(a))
  ans += abs(a)
  if a < 0:
    minus += 1

if minus%2 == 0:
  print(ans)
else:
  print(ans-mn*2)

Submission status: Accepted

Solution code:
N = int(input())
count = 0
sumation = 0
min_num = 10 ** 9 + 1
for item in input().split():
  if int(item) < 0:
    count += 1
  sumation += abs(int(item))
  min_num = min(min_num, abs(int(item)))
if count % 2 == 0:
  print(sumation)
else:
  print(sumation - 2 * min_num)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import bisect
from datetime import datetime as dt

n = input()
A = map(int, raw_input().split())
minus_count = 0
for a in A:
    if a < 0:
        minus_count += 1
ans = 0
for a in A:
    ans += abs(a)
if minus_count % 2 == 0:
    print ans
else:
    m = 10**10
    for a in A:
        if m > abs(a):
            m = abs(a)
    print ans - 2 * m

Submission status: Accepted

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

numbers_abs = [abs(n) for n in numbers]
sum_abs = sum(numbers_abs)
min_abs = min(numbers_abs)

count_negative = sum([1 for n in numbers if n < 0])

answer = sum_abs
if (count_negative % 2 == 1):
  answer = sum_abs - 2 * min_abs

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc125_d

# input
n = int(input())
A = [int(s) for s in input().split()]
# get ans
isEven = len([1 for a in A if a<0]) % 2 == 0
A = [abs(a) for a in A]
if isEven:
    ans = sum(A)
else:
    ans = sum(A) - min(A)*2
# output
print(ans)

Submission status: Accepted

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

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

if num_of_minus % 2 == 0:
    print(ans)
else:
    print(ans - 2 * min(abs_A))

Submission status: Accepted

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

for i in range(n):
    if a[i] < 0:
        b += 1
        a[i] = abs(a[i])
        
if (0 in a) or ((b % 2) == 0):
    pass
else:
    ans -= min(a) * 2

ans += sum(a)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
total = 0
c = 0
small = 1000000000
for i in range(n):
    if a[i]<0:
        c+=1
        a[i] = abs(a[i])

    small= min(small,a[i])
if c&1:
    print(sum(a)-2*small)
else:
    print(sum(a))

Submission status: Accepted

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

if sum(x < 0 for x in A) % 2 == 0:
  result = sum(map(abs, A))
else:
  minimum_abs, idx = abs(A[0]), 0
  for i in range(1, N):
    if minimum_abs > abs(A[i]):
      minimum_abs, idx = abs(A[i]), i
  result = sum(map(abs, (v for i, v in enumerate(A) if i != idx))) - abs(minimum_abs)

print(result)

Submission status: Accepted

Solution code:
input()
a = list(map(int, input().split()))
nNegative = 0
total = 0
minVal = float('inf')
for num in a:
    if num < 0:
        num *= -1
        nNegative += 1
    minVal = min(minVal, num)
    total += num
print(total if nNegative & 1 == 0 else total - 2 * minVal)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
check=sum([a<0 for a in A]) #the number of negative in A
if check%2==0:
    print(sum([abs(a) for a in A]))
else:
    dust=min([abs(a) for a in A])
    print(sum([abs(a) for a in A])-2*dust)

Submission status: Accepted

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

ans = 0
pc, zc, mc = 0, 0, 0
s = 0
min_abs = 10**9
for a in A:
    abs_a = abs(a)
    min_abs = min(min_abs, abs_a)
    s += abs_a
    if a>0:
        pc += 1
    elif a==0:
        zc += 1
    else:
        mc += 1

if zc>0 or mc%2==0:
    print(s)
else:
    print(s-2*min_abs)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve1():
    _ = int(input())
    L = list(map(int, input().split()))

    S = sum([abs(v) for v in L])
    if len(list(filter(lambda x: x < 0, L))) % 2 == 0:
        print(S)
    else:
        print(S-2*(min([abs(v) for v in L])))


def solve2():
    N = int(input())
    L = list(map(int, input().split()))
    dp = [[0]*(N+1) for _ in range(2)]
    dp[1][0] = -float('inf')
    for i in range(N):
        dp[0][i+1] = max(dp[0][i]+L[i], dp[1][i]-L[i])
        dp[1][i+1] = max(dp[0][i]-L[i], dp[1][i]+L[i])
    print(dp[0][-1])


solve2()

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    a = f()

    cntp = 0
    cntn = 0
    cnt0 = 0

    total = 0
    miabs = int(1e10)
    for i in range(n):
        total += abs(a[i])
        miabs = min(miabs, abs(a[i]))
        if a[i]>0:
            cntp += 1
        elif a[i] < 0:
            cntn += 1
        else:
            cnt0 += 1
    

    if cntn%2 == 0 or cnt0 > 0:
        print(total)
    else:
        print(total - 2*miabs)


solve()

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N = int(input())
L = list(map(int, input().split()))

S = sum([abs(v) for v in L])
if len(list(filter(lambda x: x < 0, L))) % 2 == 0:
    print(S)
else:
    print(S-2*(min([abs(v) for v in L])))

Submission status: Accepted

Solution code:
from numpy import*;_,a=open(0);a=int64(a.split());b=abs(a);print(sum(b)-sum(a<0)%2*min(b)*2)

Submission status: Accepted

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

dp = [[-float('inf')] * 2 for _ in range(n + 1)]
dp[0][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][1] + a[i], dp[i][0] - a[i])

print(dp[n][0])

Submission status: Accepted

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

minus = sum(x < 0 for x in a_l)

if minus%2==0:
    print(sum(abs(x) for x in a_l))
else:
    print(sum(abs(x) for x in a_l)-2*min(abs(x) for x in a_l))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int, input().split()))
cnt=sum(d<0 for d in a)
a=[abs(d) for d in a]
print(sum(a)-2*min(a) if cnt%2 else sum(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] = -a[i]
s = 0
m = 10**9
for i in range(n):
  s += a[i]
if c % 2 == 1:
  for i in range(n):
    m = min(m,a[i])
  s -= 2*m
print(s)

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]
# absa = list(map(abs, a))
min = min(a)
# print(cnt, a, min)
if cnt % 2 == 0:
    print(sum(a))
else:
    print(sum(a)-2*min)

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][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:
if __name__ == "__main__":
    n = int(input())
    a = map(int, input().split())
    a = list(a)
    zerop = any(map(lambda x: x == 0, a))
    evenp = sum(map(lambda x: 1 if x < 0 else 0, a)) % 2 == 0
    abss = list(map(abs, a))
    ans = 0
    if zerop or evenp:
        ans = sum(abss)
    else:
        m = min(abss)
        i = abss.index(m)
        for j, elm in enumerate(a):
            if j == i:
                ans += -abs(elm)
            else:
                ans += abs(elm)
    print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().strip())
As = list(map(int, sys.stdin.readline().strip().split()))

ans = 0
num_negative = 0
min_num = float('inf')
for A in As:
    ans += abs(A)
    min_num = min(min_num, abs(A))
    if A < 0:
        num_negative += 1
if num_negative % 2 == 1:
    ans -= 2 * min_num
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
s = 0
p = 0
m = 1000000001
for i in A:
    s += abs(i)
    if i <=0:
        p += 1
    m = min(m, abs(i))
if p % 2 == 1:
    s = s - 2 * m
print(s)