[백준-1912] 연속합 / Python

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

1912번: 연속합

n = int(input())
arr = list(map(int, input().split()))
d = [0] * n
d[0] = arr[0]
for i in range(1, n):
    d[i] = max(arr[i - 1] + arr[i], arr[i], d[i - 1] + arr[i])

print(max(d))

 

해설

간단한 DP 문제였다.

    d[i] = max(arr[i - 1] + arr[i], arr[i], d[i - 1] + arr[i])

위와 같이 핵심 규칙을 쉽게 찾을 수 있었다.😀