문제

아래와 같이 좌우로
$N$개의 장소가 있다.

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

위의 그림과 같이 배치된 경우 두 마리의 벌 모두
$4 + 1 + 4 + 9 + 9 = 27$의 꿀을 따서, 전체 꿀의 양은 54가 된다.

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은
$9 + 4 + 4 + 9 + 9 = 35$의 꿀을 따고 오른쪽 장소에서 출발한 벌은
$4 + 9 + 9 = 22$의 꿀을 따므로, 전체 꿀의 양은
$57$이 된다.

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

# 21758
import sys
input = lambda: sys.stdin.readline().strip()

# 1. 벌벌--통--꿀
# 2, 꿀--통--벌벌
# 3. 벌꿀벌

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

# 1. 벌벌--통--꿀
arr_1 = [0] * n
for i in range(1, n):
    arr_1[i] = arr_1[i-1] + arr[i]

h = 0
for i in range(1, n):
    bee1 = (arr_1[n-1] - arr[i])
    bee2 = (arr_1[n-1] - arr_1[i])
    honey = bee1 + bee2
    h = max(h, honey)
    
# 2. 꿀--통--벌벌
arr_2 = [0] * n
arr.reverse()
for i in range(1, n):
    arr_2[i] = arr_2[i-1] + arr[i]
    
for i in range(1, n):
    bee1 = (arr_2[n-1] - arr[i])
    bee2 = (arr_2[n-1] - arr_2[i])
    honey = bee1 + bee2
    h = max(h, honey)
    
# 3. 벌꿀벌
arr = [arr[i] for i in range(1, n-1)]
honey = sum(arr) + max(arr)
h = max(h, honey)

print(h)

백준 21758 꿀 따기