문제 링크

문제 해설

Idea

  • 벌이 같은 방향을 향하는 경우 상자까지의 총합에서 두 벌의 시작 위치에 있는 값을 제외
  • 벌이 다른 방향을 향하는 경우 상자까지의 총합에 절댓값을 취해서 더함

Data Size

  • N: 3 <= int <= 100,000
  • arr[i]: 1 <= int <= 10,000

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

N = int(input())
arr = list(map(int, input().split()))
forward, backward = [arr[0]]+[0]*(N-1), [0]*(N-1)+[arr[-1]]
for i in range(1,N):
    forward[i] = forward[i-1] + arr[i]
    backward[N-i-1] = backward[N-i] + arr[N-i-1]
answer = 0

for i in range(1,N-1):
    answer = max(answer, forward[N-1]*2-forward[0]-forward[i-1]-arr[i]*2)
    answer = max(answer, backward[0]*2-backward[N-1]-backward[N-i]-arr[N-i-1]*2)
    answer = max(answer, forward[i]-arr[0]+backward[i]-arr[-1])

print(answer)