[골드 5] 백준 13398 - 연속합 2 (파이썬)

https://www.acmicpc.net/problem/13398

풀이

• 주어진 수열에서 연속된 몇 개의 수를 선택해 가장 큰 합을 만든다.
• 단, 원하는 경우 수열에서 수 하나를 ‘제거’할 수 있다.
• 제거를 한 경우든 안 한 경우든 가장 큰 연속합을 구하는 문제

D, E 배열을 초기화 한다.

D = [-1e9] * N
E = [-1e9] * N

• D[i] : A[0] ~ A[i] 까지 봤을 때 “수 하나도 제거 안 하고” 가능한 최대 연속합
• E[i] : A[i] ~ A[N-1] 까지 봤을 때 “수 하나도 제거 안 하고” 가능한 최대 연속합

D배열을 채운다. (왼쪽 → 오른쪽)

D[0] = A[0]
for i in range(1, N):
    D[i] = max(A[i], A[i] + D[i - 1])

• D[0]은 시작점이니까 그냥 A[0]으로 설정.
• 이후부터는
  • 그냥 A[i]부터 새로 시작할지,
  • 앞까지 이어온 D[i-1]에 A[i]를 추가할지,
  • 둘 중 큰 값을 선택해서 저장.
• 즉, D[i] = max( A[i], A[i] + D[i-1])

E배열을 채운다. (오른쪽 → 왼쪽)

E[N - 1] = A[N - 1]
for i in range(N - 2, -1, -1):
    E[i] = max(A[i], A[i] + E[i + 1])

• E[N-1]도 끝점이니까 그냥 A[N-1]으로 설정.
• 이후부터는
  • 그냥 A[i]부터 새로 시작할지,
  • 뒤쪽 E[i+1]을 이어받아서 더할지,
  • 둘 중 큰 값을 선택.
• 즉, E[i] = max( A[i], A[i] + E[i+1])

for i in range(1, N - 1):
    answer = max(answer, D[i - 1] + E[i + 1])

• 수 하나 제거하는 경우를 체크한다.
• 제거할 수 있는 인덱스 i를 고르고, 왼쪽까지의 최대합, 오른쪽부터의 최대합을 계산한다.

코드

# 백준 13398 - 연속합 2
# 분류 : 다이나믹 프로그래밍
 
N = int(input())
A = list(map(int, input().split()))
 
D = [-1e9] * N
E = [-1e9] * N
 
D[0] = A[0]
for i in range(1, N) :
    D[i] = max(A[i], A[i] + D[i - 1])
 
E[N - 1] = A[N - 1]
for i in range(N - 2, -1, -1) :
    E[i] = max(A[i], A[i] + E[i + 1])
 
answer = max(D)
for i in range(1, N - 1) :
    answer = max(answer, D[i - 1] + E[i + 1])
 
print(answer)