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: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N = readInts()[0]
  A = readInts()
  minus = 0
  m = abs(A[0])
  s = 0
  for a in A:
    if a < 0:
      minus += 1
    if abs(a) < m:
      m = abs(a)
    s += abs(a)

  if minus % 2 == 0:
    print(s)
  else:
    print(s - m)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ans = 0
abs_mina = 10 ** 10
for i in a:
    ans += abs(i)
    abs_mina = min(abs_mina, abs(i))

if a[-1] <= 0:
    ans = ans
else:
    ans -= abs_mina * 2

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A_list = list(map(int,input().split()))
neg_num = len([x for x in A_list if x<0])
zero_num = len([x for x in A_list if x==0])
abs_list = [abs(x) for x in A_list]

ans = np.sum(abs_list)
if neg_num%2==0 or zero_num>0:
    ans = ans
elif neg_num%2!=0:
    ans = ans - min(abs_list)
print(ans)

Submission status: Wrong Answer

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

import fractions

if N == 2:
    print(fractions.gcd(A[0],A[1]))
    exit()
    
ans = []
for i in range(N):
    a = A[:i] + A[i+1:]
    for j in range(1,N-1):
        if j == 1:
            g = fractions.gcd(a[0],a[j])
        else:
            g = fractions.gcd(g,a[j])
    ans.append(g)

print(max(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
*v, = map(int,input().split())
#print(v)
c = v
mn = 0
cn = 0
flag = True
while flag:  
  for i in range(n-1):
    if c[i] < 0:
      c[i] = v[i]*(-1)
      c[i+1] = v[i+1]*(-1)
  cn = sum(c)
  if mn == cn:
    flag = False
  mn = cn
  
print(mn)

Submission status: Wrong Answer

Solution code:
def input_ints():
    return list(map(int, input().split()))

def main():
    n = int(input())
    a = input_ints()
    c = 0
    for i in range(n):
        if a[i] < 0:
            c += 1
            a[i] *= -1
    ans = sum(a)
    if c % 2:
        ans -= min(a)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#D問題
N=int(input())
A=list(map(int,input().split()))
for i in range(N-1):
    if A[i] > 0:
        pass
    else:
        A[i]=(-1*A[i])
        A[i+1]=(-1*A[i+1])
    
print(sum(A))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

import fractions

if N == 2:
    print(fractions.gcd(A[0],A[1]))
    exit()
    
ans = []
for i in range(N):
    a = A[:i] + A[i+1:]
    print(a)
    for j in range(1,N-1):
        if j == 1:
            g = fractions.gcd(a[0],a[j])
        else:
            g = fractions.gcd(g,a[j])
    ans.append(g)

print(max(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[int(i) for i in input().split()]
num=0
for i in l:
    if i<0:
        num+=1
res=0
for i in l:
    if i>0:
        res+=i
    else:
        res+=-1*i
p=10**10
for i in l:
    p=min(abs(i),p)
if num%2==0:
    A=True
else:
    A=False
if A:
    print(res)
else:
    print(res-p)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

X = sum(A)
print(X)

Submission status: Wrong Answer

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

n = input()
a = map(int, raw_input().split())
ans = 0
for i in range(n):
    ans += abs(a[i])
print ans

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A_list = list(map(int,input().split()))
n = len([x for x in A_list if x<0])
abs_list = [abs(x) for x in A_list]
ans = np.sum(abs_list)
if n%2==0:
    ans = ans
if n%2!=0:
    ans = ans - min(abs_list)
print(ans)

Submission status: Wrong Answer

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



signA = sum([1 for a in A if a<0])

absA = [abs(a) for a in A]
absA.sort()

sumA = sum(absA)
      
         
if any([a==0 for a in A]):
  print(sumA)
if signA%2==0:
  print(sumA)
if signA%2!=0:
  print(sumA - 2*absA[0])

Submission status: Wrong Answer

Solution code:

n = int(input())

arr = list(map(int,input().strip().split()))

s = sum(arr)

for i in range(n-1):
    if s-arr[i]-arr[i+1]-arr[i]-arr[i] > s:
        arr[i] = -arr[i]
        arr[i+1] = -arr[i+1]
        #print(arr)

print(sum(arr))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#全体-絶対値一番小さいやつ*2
N = int(input())
A = list(map(int,input().split()))
# N=3
# A = [-10,5,-4]
ans = 0
minnum = abs(A[0])
for i in range(N):
    ans += abs(A[i])
    minnum = min(minnum,abs(A[i]))
    #print(minnum,ans)
if N%2 == 0:
    ans -= minnum*2
print(ans)

Submission status: Wrong Answer

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

cnt = 0
flag = False
for i in range(n):
    if a[i] < 0:
        a[i] = -a[i]
        cnt += 1
    elif a[i] == 0:
        flag = True
        exit()
    else:
        continue

if flag:
    print(sum(a))
    exit()
    
if cnt % 2 == 0:
    print(sum(a))
else:
    print(sum(a) - 2*min(a))

Submission status: Wrong Answer

Solution code:
#全体-絶対値一番小さいやつ*2
N = int(input())
A = list(map(int,input().split()))
# N=3
# A = [-10,5,-4]
ans = 0
minnum = abs(A[0])
for i in range(N):
    ans += abs(A[i])
    minnum = min(minnum,abs(A[i]))
    #print(minnum,ans)
ans -= minnum*2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

count = 0
for i, x in enumerate(A):
	if x < 0:
		count += 1
		A[i] *= -1
# print(count)
if count % 2 == 0:
	print(sum(A))
else:
	print(A)
	print(sum(A)-2*min(A))

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

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

Submission status: Wrong Answer

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

if count%2==0:
    print(sum(b))
    print("ohoho")
else:
    print(sum(b)-2*min(b))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
A.sort()
B=sorted(A,key=lambda x:abs(x))
m=0
for i in range(N):
  if A[i]<0:
    m+=1
  else:
    break
ans=0
for i in range(m):
  ans-=A[i]
for i in range(m,N):
  ans+=A[i]
if m%2==1:
  ans-=B[0]*2
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int, input().split()))
m = 0
low = l[0]
s = 0
for i in range(n):
  if l[i] < 0:
    l[i] = abs(l[i])
    m += 1
  if low > l[i]:
    low = l[i]
  s += l[i]
if m%2:
  s -= low*2
print(s)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ans = 0
    for i in range(N-1):
        if A[i] < 0:
            A[i] *= -1
            A[i+1] *= -1
    # print(A)

    return sum(A)


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ans = 0
    for i in range(N-1):
        if A[i] < 0:
            A[i] *= -1
            A[i+1] *= -1
    print(A)

    return sum(A)


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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]*(-1)
if cnt % 2 == 0:
    for a in A:
        ans = sum(A)
else:
    ans = sum(A) - 2*min(A)
print(ans)

Submission status: Time Limit Exceeded

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


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

Solution code:
import itertools

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

pat = []
for i in range(N-1):
    pat.extend(itertools.combinations([i for i in range(N-1)],i+1))
B = A.copy()
B_list = [A.copy()]

for j in pat:
    for i in j:
        A[i:i+2] = [i * (-1) for i in A[i:i+2]]

    B_list.append(A)
    A = B.copy()
total = 0
for i in B_list:
    if total < sum(i):
        total = sum(i)
print(total)

Submission status: Time Limit Exceeded

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

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

while True:
  A.sort()
  cr = A[0] + A[1]
  if cr < 0:
    A[0] *= -1
    A[1] *= -1
  else:
    break
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
while True:
  mi = min(A)
  mid = A.index(mi)
  A[mid] = -mi
  mi2 = min(A)
  if mi + mi2 >= 0:
    A[mid] = mi
    break
  else:
    mid2 = A.index(mi2)
    A[mid2] = -mi2
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):
    abs_a = list(map(abs, A))
    min_a = min(abs_a)
    for i in range(N-1):
        if A[i] < 0:
            A[i] = -A[i]
            A[i+1] = -A[i+1]
if A[N-1] < 0:
    print(sum(abs_a) - min_a * 2) 
else:
    print(sum(abs_a))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
ans=sum(a)
for i in range(n//2):
  a[i*2]*=-1
  a[i*2+1]*=-1
  ans=max(ans,sum(a))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int(input())
A = list(map(int, input().split()))
heapq.heapify(A)
while True:
  m = heapq.heappop(A)
  n = heapq.heappop(A)
  if m + n > 0:
    heapq.heappush(A, m)
    heapq.heappush(A, n)
    break
  else:
    heapq.heappush(A, -m)
    heapq.heappush(A, -n)
print(sum(A))

Submission status: Time Limit Exceeded

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

mp = 1
EvenOdd = ""
sm = 0
for i in range(len(a)):
    sm += abs(a[i])
    mp *= a[i]
if mp < 0:
    min_a = min(abs(a[i]) for i in range(len(a)))
    print(sm - min_a*2)        
else:
    print(sm)

Submission status: Time Limit Exceeded

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

mp = 1
EvenOdd = ""
for i in range(len(a)):
    mp *= a[i]
    if mp < 0:
        EvenOdd = "Odd"
    else:
        EvenOdd = "Even"

sm = 0
for i in range(len(a)):
    sm += abs(a[i])
if EvenOdd == "Even":
    print(sm)
else:
    min_a = min(abs(a[i]) for i in range(len(a)))
    print(sm - min_a*2)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)

n = int(input())
a = list(map(int, input().split()))
# dp = [None]*(n+1)
#dp = [[None]*(n+1) for _ in range(2)]
dp = [[None]*(2) for _ in range(n+1)]

def solve(a):
    if len(a) == 0:
        return 0
    elif len(a) == 1:
        return a[0]
    elif len(a) == 2:
        v1 = a[0] + a[1]
        v2 = -a[0] - a[1]
        return max(v1, v2)

    v1 = a[0] + solve(a[1:])
    v2 = -a[0] + solve([-a[1]] + a[2:])
    return max(v1, v2)

def solve(a, flg):
    l = len(a)
    if dp[l][flg] is not None:
        return dp[l][flg]

    if flg == 1:
        a[0] = -a[0]

    if l == 0:
        dp[l][flg] = 0
    elif l == 1:
        dp[l][flg] = a[0]
    elif l == 2:
        v1 = a[0] + a[1]
        v2 = -a[0] - a[1]
        dp[l][flg] = max(v1, v2)
    else:
        v1 = a[0] + solve(a[1:], 0)
        v2 = -a[0] + solve(a[1:], 1)
        dp[l][flg] = max(v1, v2)
        # if flg == 0:
        #     v1 = a[0] + solve(a[1:], flg)
        #     v2 = -a[0] + solve(a[1:], abs(flg - 1))
        #     dp[l][flg] = max(v1, v2)
        # else:
        #     v1 = -a[0] + solve(a[1:], flg)
        #     v2 = a[0] + solve(a[1:], abs(flg - 1))
        #     dp[l][flg] = max(v1, v2)

    return dp[l][flg]

#def solve(idx):
print(solve(a, 0))
#print(solve(a, 1))
#print(solve(a, 0))
# v1 = solve(a, 1)
# v2 = solve(a, 0)
#
# print(v1, v2)
# print(max(v1, v2))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)

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

def solve(a):
    if len(a) == 0:
        return 0
    elif len(a) == 1:
        return a[0]
    elif len(a) == 2:
        v1 = a[0] + a[1]
        v2 = -a[0] - a[1]
        return max(v1, v2)

    v1 = a[0] + solve(a[1:])
    v2 = -a[0] + solve([-a[1]] + a[2:])
    return max(v1, v2)

# for i in range(n-1):
#     v1 = a[i] + a[i+1]
#     v2 = -a[i] - a[i+1]
#     if v2 > v1:
#         a[i] = -a[i]
#         a[i+1] = -a[i+1]

# print(a)
# print(sum(a))

print(solve(a))

Submission status: Time Limit Exceeded

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


def solve(N: int, A: "List[int]"):
    switch_count = N if N%2 == 0 else N-1
    A.sort()
    sumA = sum(A)
    answer = 0
    for i in range(0,switch_count+1,2):
        a = sumA
        a += sum([-j for j in A[:i]])*2
        answer = max(a,answer)
    print(answer)

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

Solution code:
import sys
sys.setrecursionlimit(10**6)

def dp(i,is_reverse):
  if i == 0:
    if is_reverse == 0: return 0
    else: return -float('inf')
  else:
    if is_reverse == 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 = int(input())
A = list(map(int,input().split()))
print(dp(N,0))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
for i in range(n):
    count = len([x for x in filter(lambda n: n<0, a)])
b = [x for x in map(abs, a)]

p = min(b)
q = sum(b)
if count % 2 != 0:
    ans = q - 2 * p
else:
    ans = q
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


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

    def dp(i, j):
        if i == 0 and j == 0:
            return 0
        if i == 0 and j == 1:
            return -float('inf')
        if j == 0:
            return max(dp(i - 1, 0) + a[i - 1], dp(i - 1, 1) - a[i - 1])
        if j == 1:
            return max(dp(i - 1, 0) - a[i - 1], dp(i - 1, 1) + a[i - 1])

    score = dp(n, 0)

    print(score)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)


def dp(i, j):
    if i == 0:
        if j:
            return -float('inf')
        else:
            return 0
    if j:
        return max(dp(i-1, False) - a[i-1], dp(i-1, True) + a[i-1])
    else:
        return max(dp(i-1, False) + a[i-1], dp(i-1, True) - a[i-1])


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

Submission status: Time Limit Exceeded

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

p_m=1
for n in range(N):
    p_m*=LA[n]
    
LA_absolute=[i*(-1) if i<0 else i for i in LA]


if p_m>=0:
    print(sum(LA_absolute))
else:
    print(sum(LA_absolute)-2*min(LA_absolute))

Submission status: Time Limit Exceeded

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

p_m=1
for n in range(N):
    p_m*=LA[n]
    
LA_absolute=[i*(-1) if i<0 else i for i in LA]


if p_m>=0:
    print(sum(LA_absolute))
else:
    LA_absolute.sort()
    print(sum(LA_absolute)-2*LA_absolute[0])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import numpy as np


n = int(raw_input())
 
A_list = map(int,raw_input().split())

minus_sum = sum(x<0 for x in A_list)

arr_A = np.array(A_list)
abs_arr = np.abs(arr_A)
ABS_list = abs_arr.tolist()
#print ('ABS_list',ABS_list)


min_id = [i for i, x in enumerate(ABS_list) if x == min(ABS_list)]

if(minus_sum%2 == 0):
	print sum(ABS_list)
else:
	print sum(ABS_list)-ABS_list[min_id[0]]-ABS_list[min_id[0]]

Submission status: Time Limit Exceeded

Solution code:
def getNumNeg(L):
    return sum([i<0 for i in L])

def findmax(L):
    numNeg = getNumNeg(L)
    if numNeg % 2 == 0: # end-point: all positive
        while getNumNeg(L) != 0:
            i = L.index(min(L[:-1]))
            j = i + 1
            L[i] = L[i] * (-1)
            L[j] = L[j] * (-1)
        print(sum(L))
    else: # end-point: smallest abs(number) is negative
        absL = list(map(abs, L))
        stop = min(absL)*(-1)
        while (getNumNeg(L) != 1) or (min(L) != stop):
            i = L.index(min(L[:-1]))
            j = i + 1
            L[i] = L[i] * (-1)
            L[j] = L[j] * (-1)
        print(sum(L))

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
from itertools import combinations
import copy
b=[i for i in range(n-1)]
c=[v for i in range(1,n) for v in combinations(b, i)]
sum_temp=sum(a)
for v in c:
    a_temp=copy.copy(a)
    for i in v:
        a_temp[i]*=-1
        a_temp[i+1]*=-1
    if sum_temp<sum(a_temp):
        sum_temp=sum(a_temp)
print(sum_temp)

Submission status: Time Limit Exceeded

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

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


for i in range(0,N):
  if A[i]<0:
    n=n+1
    AA=A.pop(i)
    A.insert(i,(-1)*AA)
    sm=sm+AA*(-1)
    if (-1)*AA<mn:
      mn=(-1)*AA
  else:
    sm=sm+A[i]
    if A[i]<mn:
      mn=A[i]

if n%2==0:
  print(sm)
else:
  print(sm-2*mn)

Submission status: Time Limit Exceeded

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

n=0
for i in range(0,N):
  if A[i]<0:
    n=n+1
    AA=A.pop(i)
    A.insert(i,(-1)*AA)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 
N = int(input())
A =list(map(int, input().strip().split()))
Ap = np.abs(A)
i = 0
m = 0
s = 0
M = 0
while i <= N - 1:
    if A[i] < 0:
        m += 1
    i += 1
if m % 2 == 0:
    M = np.sum(Ap)
if m % 2 == 1:
    while s <= N - 1:
        M1 = np.sum(Ap) - 2 * Ap[s]
        if M1 >= M:
            M = M1
        s += 1
print(M)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 
N = int(input())
A =list(map(int, input().strip().split()))
Ap = np.abs(A)
i = 0
m = 0
s = 1
while i <= N - 1:
    if A[i] < 0:
        m += 1
    i += 1
if m % 2 == 0:
    M = np.sum(Ap)
if m % 2 == 1:
    M = np.sum(Ap) - 2 * Ap[0]
    while s <= N - 1:
        M1 = np.sum(Ap) - 2 * Ap[s]
        if M1 > M:
            M = M1
        s += 1
print(M)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
li = list(map(int,input().split()))

for i in range(len(li) - 1):
    if i == 0 and li[i] < 0:
        li[i] *= -1
        li[i + 1] *= -1        

    elif sum(li[:i + 1]) < sum(li[:i]) + (li[i] * -1):
        li[i] *= -1
        li[i + 1] *= -1

print(sum(li))

Submission status: Time Limit Exceeded

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

prev = sum(data)

while True:
    data = sorted(data)

    data[0] = -data[0]
    data[1] = -data[1]

    cur = sum(data)
    if prev >= cur:
        break

    prev = cur

print(prev)

Submission status: Time Limit Exceeded

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

nums = A[:]
import math

gcd_queue = [
    (0, nums[0]),
]
for n in nums[1:]:
    tmp_queue = []
    for q in gcd_queue:
        tmp_queue.append((q[0] + q[1], n))
        tmp_queue.append((q[0] + q[1]*-1, n*-1))
    gcd_queue = set(tmp_queue[:])
    #print(gcd_queue)

gcd_queue = list(gcd_queue)
ans = gcd_queue[0][0] + gcd_queue[0][1]
for q in gcd_queue:
    ans = max(ans, q[0]+q[1])
print(ans)

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:
n = int(input())
a = list(map(int, input().split()))
a.sort()
max = sum(a)
for i in range(0,n-1):
    a[i] *= -1
    a[i+1] *= -1
    if max < sum(a):
        max  = sum(a)
        a[i] *= -1
        a[i + 1] *= -1
    a[i] *= -1
    a[i+1] *= -1
print(max)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
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:
from functools import lru_cache
import sys

sys.setrecursionlimit(10000000)

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


@lru_cache(maxsize=None)
def rec(i, reverse):
    if i == N - 1:
        return A[i] * reverse

    num_normal = rec(i + 1, 1) + (A[i] * reverse)
    num_reverse = rec(i + 1, -1) + (-1 * A[i] * reverse)

    return max(num_normal, num_reverse)


print(rec(0, 1))

Submission status: Time Limit Exceeded

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

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


print(max(max(x),sum(a)))

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
  else:break

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

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


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

Submission status: Time Limit Exceeded

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

a.sort()
i = 0
while a[i+1] < -a[i]:
      a[i+1] *= -1
      a[i] *= -1
      a.sort()
sum = 0
for i in range(n):
      sum += a[i]
print(sum)