CodeForce #849 (Div. 4) E. Negatives and Positives

 

수열에서 인접한 수 2개의 부호를 동시에 바꿔주는 동작들을 수행하여 만들어질 수 있는 최대합 값을 구하는 문제이다.

인접한 두 수의 부호가 다를 때 동시에 바꿔주는 동작은 음의 부호( - )가 옆으로  이동하는 것으로 볼 수 있으며

만약 인접한 두 수가 음수,음수이면 양수,양수로 무조건 바뀌어야한다.

위의 과정을 반복하면 전체 수열에서 음의 개수가 짝수이면 모든 수가 다 양수로 바뀌고,

음의 개수가 홀수면 가장 작은 수만 음수이고 나머지 수들은 다 양수가 된다.

 

import sys
input=sys.stdin.readline
 
t=int(input())
 
for _ in range(t):
    n=int(input())
    num=list(map(int, input().split()))  
    
    negCnt=0
    for i in range(n):
        if num[i] < 0:
            negCnt+=1
    sum=0
    if negCnt%2 == 0:
        for i in range(n):
            if num[i]<0:
                sum+=(-num[i])
            else:
                sum+=num[i]
        print(sum)
    else:
        minAbs=10**9
        for i in range(n):
            if num[i]<0:
                sum+=(-num[i])
                if minAbs > -num[i]:
                    minAbs = -num[i]
            else:
                sum+=num[i]
                if minAbs > num[i]:
                    minAbs = num[i]
        print(sum-minAbs*2)