[백준] 1912번, 연속합 (Python)

문제

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

1912번: 연속합

 

코드

n = int(input())
total = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dp[0] = total[0]

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

DP문제이고, 연속된 몇개의 수를 선택하여 가장 큰 값을 출력하는 문제이다.

 

연속된 값을 더한값이 더 클 수도 있고 더하지 않은 값이 더 클수도 있다.

1부터 확인하면서 dp에 값을 채워주면 된다.