[백준] 1912 - 연속합 [Python(파이썬)]

문제

www.acmicpc.net/problem/1912

1912번: 연속합

풀이

n의 범위가 크므로(최대 100,000) O(n)시간 안에 문제를 해결하는 것이 중요하다.

따라서 동적계획법을 적용하여 풀 수 있다.

 

최적해는 아래의 두 가지 상황을 고려하여 구할 수 있다.

 

1) 계속해서 더해간다: 이전 연속합에서 현재 정수를 더한다. 

2) 초기화한다: 현재 정수부터 연속합을 다시 구한다.

 

점화식은 dp[n] = max(dp[n-1]+dp[n], dp[n])이 된다.

그림으로 표현하면 다음과 같다.

 

 

코드

import sys

n = int(sys.stdin.readline().strip())
dp = [0] + [int(x) for x in sys.stdin.readline().split()]

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

print(max(dp[1:]))