[Python] 연속합 - 백준 (DP)

해당 글은 백준 1912번 문제 '연속합'을 다룬다.

문제

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

1912번: 연속합

 

설명

해당 문제는 완전 탐색으로 풀면 시간 초과가 뜬다. DP로 해결하면 빠른 시간안에 해결할 수 있다.

정수의 갯수 만큼 for문을 돌려 '이전의 모든 숫자 합들 중 최댓값'에 현재값을 더한 값과 현재값을 비교해서 큰 값으로 업데이트를 시켜준다.

즉, 점화식은 아래와 같이 표현된다.

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

     

 

코드

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