Problem:


Score : 400 points

Problem Statement

There are N integers, A_1, A_2, ..., A_N, arranged in a row in this order.

You can perform the following operation on this integer sequence any number of times:

Operation: Choose an integer i satisfying 1 \leq i \leq N-1. Multiply both A_i and A_{i+1} by -1.

Let B_1, B_2, ..., B_N be the integer sequence after your operations.

Find the maximum possible value of B_1 + B_2 + ... + B_N.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

-10^9 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible value of B_1 + B_2 + ... + B_N.

Sample Input 1

3
-10 5 -4

Sample Output 1

19

If we perform the operation as follows:

Choose 1 as i, which changes the sequence to 10, -5, -4.

Choose 2 as i, which changes the sequence to 10, 5, 4.

we have B_1 = 10, B_2 = 5, B_3 = 4. The sum here, B_1 + B_2 + B_3 = 10 + 5 + 4 = 19, is the maximum possible result.

Sample Input 2

5
10 -4 -8 -11 3

Sample Output 2

30

Sample Input 3

11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000

Sample Output 3

10000000000

The output may not fit into a 32-bit integer type.



Sample input:
3
-10 5 -4


Sample output:
19

Submission status: Accepted

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

dp = [[0]*2 for i in range(n)]

dp[0][0] = A[0]
dp[0][1] = -A[0]

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

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

Submission status: Accepted

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

minus = 0
zero = 0

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

A2 = [abs(i) for i in A]
if minus %2 == 0 or zero >= 1:
    print(sum(A2))
else:
    print(sum(A2)-2*min(A2))

Submission status: Accepted

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


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

_min = 10**9 + 1
flag = False  # if minus integers is odd, flag is True
_sum = 0

for a in A:
    _sum += abs(a)
    _min = min(_min, abs(a))
    if a < 0:
        flag = not flag

if flag:
    _sum -= _min * 2
print(_sum)

Submission status: Accepted

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

min_abs = 10**9
abs_sum = 0
minus_cnt = 0
zero_cnt = 0
for a in al:
    if a < 0: minus_cnt+=1
    elif a == 0: zero_cnt+=1
    abs_sum += abs(a)
    min_abs = min(min_abs, abs(a))

if minus_cnt%2 == 0:
    print(abs_sum)
else:
    if zero_cnt > 0:
        print(abs_sum)
    else:
        print(abs_sum-min_abs*2)

Submission status: Accepted

Solution code:
import math
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import product
from collections import defaultdict
from collections import deque
from collections import Counter
import heapq


def input_li():
    return list(map(int, input().split()))


def input_int():
    return int(input())


N = input_int()
A_LI = input_li()
dp = [[0] * 2 for _ in range(N)]
dp[0][0] = A_LI[0]
dp[0][1] = -A_LI[0]
for i in range(1, N):
    dp[i][0] = max(dp[i - 1][0] + A_LI[i], dp[i - 1][1] - A_LI[i])
    dp[i][1] = max(dp[i - 1][0] - A_LI[i], dp[i - 1][1] + A_LI[i])
print(dp[-1][0])

Submission status: Accepted

Solution code:
import math
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import product
from collections import defaultdict
from collections import deque
from collections import Counter
import heapq


def input_li():
    return list(map(int, input().split()))


def input_int():
    return int(input())


N = input_int()
A_LI = input_li()
minus_cnt = 0
for a in A_LI:
    if a < 0:
        minus_cnt += 1

ans = 0
abs_min = 10 ** 9
for a in A_LI:
    ans += abs(a)
    abs_min = min(abs_min, abs(a))
print(ans) if minus_cnt % 2 == 0 else print(ans - abs_min * 2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
for i in range(n - 1):
    if a[i] < 0:
        a[i] *= -1
        a[i + 1] *= -1
print(sum(a) - 2 * min(abs(i) for i in a) - 2 * a[-1] if a[-1] < 0 else sum(a))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

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

dp[-1][0] = dp[-2][0]-As[-1]
dp[-1][1] = dp[-2][1]+As[-1]

print(max(dp[-1]))

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 = [abs(a) for a in A]
if cnt % 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()))
m = 0
z = 0
for i in range(N):
    if A[i]<0:
        m += 1
    elif A[i]==0:
        z += 1
m = m%2
B = sorted([abs(A[i]) for i in range(N)])
p = m-z
if p>0:
    for i in range(z,z+p):
        B[i] = -B[i]
    print(sum(B))
else:
    print(sum(B))

Submission status: Accepted

Solution code:
n=int(input())

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

plus = []

minas = []

for value in a:
    if value < 0:
        minas.append(abs(value))
    else:
        plus.append(value)

if len(minas)%2 == 0:
    ans = sum(plus)+sum(minas)
else:
    if len(plus) > 0:
        mini = min(min(plus),min(minas))
        ans = sum(plus)+sum(minas)-mini*2
    else:
        mini = min(minas)
        ans = sum(minas)-mini*2

print(ans)

Submission status: Accepted

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

cnt = len([a for a in A if a < 0])
if cnt % 2 == 0:
    print(sum([abs(a) for a in A]))
else:
    ans = sum([abs(a) for a in A])
    M = float('inf')
    for a in A:
        if abs(a) < M:
            M = abs(a)
    print(ans - 2 * M)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

if cnt%2==0:
    print(sum(abs(Ai) for Ai in A))
else:
    A.sort(key=lambda x: abs(x))
    print(-abs(A[0])+sum(abs(Ai) for Ai in A[1:]))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque

INF = 1 << 50



def run():
    N, *A = map(int, read().split())

    SUM = sum([abs(a) for a in A])
    if A.count(0):
        print(SUM)
        return

    do = [0]
    for a in A[:-1]:
        if not do[-1]:
            if a > 0:
                do.append(0)
            else:
                do.append(1)
        else:
            if a > 0:
                do.append(1)
            else:
                do.append(0)

    if A[-1] > 0:
        if do[-1]:
            base_ans = SUM - abs(A[-1]) * 2
        else:
            print(SUM)
            return
    else:
        if do[-1]:
            print(SUM)
            return
        else:
            base_ans = SUM - abs(A[-1]) * 2
    ans = base_ans
    for i in range(N-1):
        ans = max(ans, base_ans - abs(A[i]) * 2 + abs(A[-1]) * 2)

    print(ans)





if __name__ == "__main__":
    run()

Submission status: Accepted

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

Submission status: Accepted

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

# In[8]:


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


# In[9]:


a_abs = list(map(abs,A))
minus_cnt = sum([1 for x in A if x < 0])
if minus_cnt%2 == 0:
    ans = sum(a_abs)
else:
    ans = sum(a_abs) - min(a_abs)*2
print(ans)


# In[ ]:

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[0 for _ in range(2)] for _ in range(n+1)]
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())
a = list(map(int, input().split()))

ans, count = 0, 0
for i in range(n):
    ans += abs(a[i])
    if a[i] < 0:
        count += 1
a = list(abs(i) for i in a)
if count%2 != 0:
    ans -= 2*min(a)
print(ans)

Submission status: Accepted

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

b = list(map(abs, a))
if cnt%2 == 0:
  print(sum(b))
else:
  print(sum(b)-2*min(b))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
## https://atcoder.jp/contests/abc125/tasks/abc125_d

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

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

dp[1][False] = N_List[0] + N_List[1]
dp[1][True] = (N_List[0] + N_List[1])*(-1)

for i in range(2,N):
    dp[i][False] = max(dp[i-1][True] + N_List[i],dp[i-1][False] + N_List[i])
    dp[i][True] = max(dp[i-1][True] + N_List[i-1]*2 + N_List[i]*(-1) ,
                      dp[i-1][False] + N_List[i-1]*(-2) + N_List[i]*(-1))

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

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(n):
  if a[i]<0:
    check=check+1
a=list(map(lambda x:abs(x),a))

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

Submission status: Accepted

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

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

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[N][0])

Submission status: Accepted

Solution code:
n = int(input())
a_list = [int(x) for x in input().split()]
count = 0
ans = 0
m = 10 ** 9
for i in range(n):
    if a_list[i] < 0:
        a_list[i] *= -1
        count += 1
    ans += a_list[i]
    if a_list[i] < m:
        m = a_list[i]
if count % 2 == 1:
    ans -= m * 2
print(ans)

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] = -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()))
import bisect
a.sort()

idx = bisect.bisect_left(a, 0)
sm = [abs(x) for x in a]
if idx % 2 == 0:
    print(sum(sm))
else:
    print(sum(sm) - 2*min(sm))

Submission status: Accepted

Solution code:
import sys

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


ans = 0
for a in A:
    ans += abs(a)

c = 0
m = abs(A[0])
for a in A:
    if a < 0:
        c += 1
    elif a == 0:
        print(ans)
        sys.exit()

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

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

Submission status: Accepted

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

A_tmp = sorted(A, key=abs, reverse=True,)
total = 0
for i,v in enumerate(A_tmp):
    if (v <= 0) and (i < len(A_tmp)-1):
        v *= (-1)
        A_tmp[i+1] = (-1) * A_tmp[i+1]
    total += v
print(total)

Submission status: Accepted

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

A_tmp = sorted(A, key=abs, reverse=True,)
total = 0
for i,v in enumerate(A_tmp):
    if (v <= 0) and (i < len(A_tmp)-1):
        A_tmp[i] = (-1) * A_tmp[i]
        A_tmp[i+1] = (-1) * A_tmp[i+1]
        total += A_tmp[i]
    else:
        total += v
print(total)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 符号の数について、-が偶数だった場合、全てを打ち消せる
# 奇数だった場合、どれか一つが残る。
# `..,+,-,+,..`を→移動←移動できるので

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    ret = sum(abs(a) for a in A)
    num_neg = sum(a < 0 for a in A)
    min_abs_A = min(abs(a) for a in A)
    if num_neg % 2 == 1:
        ret -= 2*min_abs_A
        
    print(ret)
    
solve()

Submission status: Accepted

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

N = int(input())
A = list(map(int,input().split()))
cnt = 0
for i,a in enumerate(A):
    if a<0:
        cnt += 1
        A[i] = -1*a
A = sorted(A)
print(sum(A)-2*A[0]*(cnt%2))

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

idx = bisect_left(A,0)
if idx != 0 and idx != N:
  if idx % 2 == 1:
    if abs(A[idx-1]) > abs(A[idx]):
      A[idx-1] *= -1
      A[idx] *= -1
  for i in range(0,idx-1,2):
    A[i] *= -1
    A[i+1] *= -1

if idx==N:
  if N % 2 == 0:
    print(-sum(A))
    exit()
  else:
    print(-sum(A[:-1])+A[-1])
    exit()

print(sum(A))

Submission status: Accepted

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

sum = 0
pm = 0
min = 10**10
for xi in range(n):
    if a[xi]<0: pm+=1
    sum += abs(a[xi])
    if abs(a[xi])<min :min=abs(a[xi])
    # print(a[xi], sum, min)

if pm%2 ==1: sum-=min*2

print(sum)

Submission status: Accepted

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

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


print(max(dp1[-1], dp2[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
la = [int(w) for w in input().split()]

ans = sum([abs(w)for w in la])
if len([w for w in la if w < 0]) % 2 == 0:
    print(ans)
    exit()

sla = sorted([abs(w)for w in la])
ans -= sla[0]*2
print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
a = lr()
dp = [[0 for  j in range(2)] for i in range(n+1)]
dp[1][1] = -a[0]
dp[1][0] = a[0]
for i in range(1,n-1):
    dp[i+1][1] = max(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])
print(max(dp[n-1][1]-a[n-1], dp[n-1][0]+a[n-1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
l=[*map(int,input().split())]
c=0
for e,i in enumerate(l):
  if i<0:
    c+=1
    l[e]=-i
print(sum(l)-[0,min(l)*2][c%2])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = [abs(i) for i in A]
ans1 = sum(B) - 2 * min(B)
for i in range(N - 1):
    if A[i] < 0:
        A[i] = -A[i]
        A[i + 1] *= -1
ans2 = sum(A)
ans = max(ans1, ans2)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
dp=[[0]*2 for i in range(N+1)]
dp[0][1]=-10**30
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 = list(map(int,input().split()))

# dp[i][j] = i個目とi - 1個目に対して、j(True:反転させた, False:元のまま)の状態でのi個目までの最大値

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

dp[0][False] = None
dp[0][True] = None
dp[1][False] = A[0] + A[1]
dp[1][True] = (A[0] + A[1]) * (-1)

for i in range(2, len(dp)):
  dp[i][False] = max(dp[i - 1][False] + A[i], dp[i - 1][True] + A[i])
  dp[i][True] = max(dp[i - 1][False] - A[i - 1] * 2 - A[i], dp[i - 1][True] + A[i - 1] * 2 - A[i])

print(max(dp[N - 1][False], dp[N - 1][True]))

Submission status: Accepted

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

b = [abs(i) for i in a]

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

Submission status: Accepted

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

b = [abs(i) for i in a]

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
S = sum(map(abs, A))
 
cnt = 0
 
for a in A:
    if a > 0:
        cnt += 1
        
if (len(A)-cnt)%2==0 or 0 in A:
    print(S)
else:
    print(S-2*min(map(abs, A)))

Submission status: Accepted

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

count = 0
min = abs(A[0])
sum = 0
for i in A:
    # 0と負の数をカウント
    if i<=0:
        count += 1
    # 最小更新
    if min > abs(i):
        min = abs(i)
    # 合計
    sum += abs(i)
#print('count:'+str(count))
#print('min:'+str(min))
#print('sum:'+str(sum))
if count%2 == 0:
    print(sum)
else:
    print(sum-(min*2))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    total = 0
    mi = f_inf
    cnt_minus = 0
    for a in A:
        if a < 0:
            cnt_minus += 1
        if mi > abs(a):
            mi = abs(a)
        total += abs(a)
    print(total if cnt_minus % 2 == 0 else total - mi * 2)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
a = lr()
ans = []
zeroflag = False
neg = 0
for num in a:
    if num == 0:
        zeroflag = True
    if num < 0:
        neg+=1
    ans.append(abs(num))
if zeroflag:
    print(sum(ans))
else:
    ans.sort()
    if neg%2 == 0:
        print(sum(ans))
    else:
        print(sum(ans[1:])-ans[0])

Submission status: Accepted

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    n = int(input())
    a = list(map(int, input().split()))
    s, m = 0, 10**18
    flag = 1
    for x in a:
        s += abs(x)
        flag ^= (x<0)
        m = min(m, abs(x))

    if flag or (0 in a):
        print(s)
    else:
        print(s-2*m)
        
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
smallest = 10 ** 9 + 1
nega = 0
for i in range(len(A)):
  if A[i] < 0:
    nega ^= 1
    A[i] *= -1
  ans += A[i]
  if A[i] < smallest:
    smallest = A[i]
  
if nega:
  ans -= smallest * 2
  
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    m = 0
    for i in range(n):
        if a[i]<0:
            m += 1
    ans = 0
    for i in range(n):
        ans += abs(a[i])
    if m%2==0:
        print(ans)
    else:
        mi = float('inf')
        for i in range(n):
            if mi>abs(a[i]):
                mi = abs(a[i])
        print(ans-2*mi)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

cnt = 0
m = 0
for a in As:
  if a < 0:
    cnt += 1
    
if cnt % 2 == 0:
  print(sum(map(abs, As)))
else:
  print(sum(map(abs, As))-2*min(map(abs, As)))

Submission status: Accepted

Solution code:
import numpy as np

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

if np.count_nonzero(a < 0) % 2 == 0:
    print(np.abs(a).sum())
else:
    b = np.abs(a)
    m = b.min()
    print(b.sum() - 2 * m)

Submission status: Accepted

Solution code:
N = int(input())

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

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

Submission status: Accepted

Solution code:
n = int(input())
aas = list(map(int, input().split()))
cnt = 0
res = 0
mini = float('inf')
for i in aas:
    if i < 0:
        cnt += 1
    res += abs(i)
    mini = min(mini, abs(i))
if cnt%2 == 0:
    print(res)
    exit()
print(res - mini*2)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=0
ans=0
mini=10000000000
for i in a:
    if i<0:
        cnt+=1
    p=abs(i)
    ans+=p
    if p<mini:
        mini=p
if cnt%2==1:
    ans-=mini*2
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
import numpy as np  # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    A = LI()

    dp = np.zeros((N + 1, 2), np.float64)
    dp[0, 1] = -INF  # A[0]より左は存在しないためdp[0, 1]からの派生は存在しない （初期状態でA[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)

    # dp[N, 1]は操作できないため存在しない
    print(int(dp[N, 0]))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    A = LI()

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

    if minus % 2 == 0:
        ans = sum(map(lambda x: abs(x), A))
    else:
        ans = 0
        mn = INF
        for a in A:
            ans += abs(a)
            mn = min(mn, abs(a))
        ans -= 2 * mn

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = [int(i) for i in input().split()]
    cntM = 0
    for i in range(N):
        if A[i] < 0:
            A[i] *= -1
            cntM += 1
    if 0 in A or cntM % 2 == 0:
        print(sum(A))
    else:
        print(sum(A) - min(A) * 2)

resolve()

Submission status: Accepted

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

cnt = 0

for a in A:
    if a > 0:
        cnt += 1
        
if (len(A)-cnt)%2==0 or 0 in A:
    print(S)
else:
    print(S-2*min(map(abs, A)))