백준 13398 - 연속합 2

문제 링크 : https://www.acmicpc.net/problem/13398

 

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이 과정

수열에서 수를 하나 제거하거나 제거하지 않았을 때의 부분 연속합을 구해야 한다.

 

왼쪽에서 오른쪽으로 값이 더해지는 최대 연속합 DP 배열과 오른쪽에서 왼쪽으로 값이 더해지는 최대 연속합 DP 배열을 만들어, i 번째 수를 제거했을 때를 "i-1 까지의 왼쪽->오른쪽 최대 연속합"과 "i+1 까지의 왼쪽<-오른쪽 최대 연속합을 더한 값"으로 구현했다. 수를 제거하지 않았을 때는 왼쪽->오른쪽 최대 연속합 배열과 오른쪽->왼쪽 최대 연속합 배열의 최댓값을 사용했다.

# 13398. 연속합 2 ( GOLD 5 )

import sys
input = sys.stdin.readline

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

dp_left = [arr[i] for i in range(n)]
dp_right = [arr[i] for i in range(n)]

for i in range(1, n): dp_left[i] = max(dp_left[i], dp_left[i-1] + dp_left[i])
for i in range(n-2, -1, -1): dp_right[i] = max(dp_right[i], dp_right[i+1] + dp_right[i])

result = max(max(dp_left), max(dp_right)) # 제거하지 않았을 때
for i in range(1, n-1):
  result = max(result, dp_left[i-1] + dp_right[i+1])

print(result)