[코딩인터뷰] 백준 13398번 연속합 2

백준 13398번 연속합 2

import sys
readline = sys.stdin.readline
read = sys.stdin.read

N = int(readline())
A = list(map(int, readline().split()))
A.insert(0,0)

answer = -(10**10)
d = [[answer] * (N+1) for _ in range(2)]
for k in range(1, N+1):
    # 일반적인 누적합을 계산하는 부분
    # 'd[0][k-1] + A[k]' 는 이전 누적합 중 최대값과 현재 값을 더했을 경우
    d[0][k] = max(d[0][k-1] + A[k], A[k])
    # 'd[0][k-1]' 는 지금 A[k] 를 누적합 계산에서 제외할 경우
    # 'd[1][k-1] + A[k]' 는 이전에 특정 숫자를 누적합에서 제외한 값들 중 최대값에 현재 값을 더했을 경우
    d[1][k] = max(d[0][k-1], d[1][k-1] + A[k])
    answer = max(answer, max(d[0][k], d[1][k]))

print(answer)