백준 /1912번 / 연속합 / python 파이썬

 

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

 

내 답안

n = int(input())
num = list(map(int, input().split()))

dp = [0] * n
dp[0] = num[0]

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

 

다이나믹 프로그래밍(DP)으로 해결할 수 있는 문제이다. 

현재 숫자를 포함해 앞에서부터 더해온 값과 현재 값을 비교했을 때, 현재 숫자가 크다면 앞에서 더해온 값은 총합을 키우는데 의미가 없다. 따라서 현재까지 더해온 값을 DP 테이블에 저장하고 현재 값과 비교해가면서 문제를 해결할 수 있다.