[파이썬, Python] 백준 1912: 연속합

문제

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

1912번: 연속합

코드

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

dp = [-1001] * (n+1)

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

설명

우선 입력을 각각 받아준다.

그리고 dp를 -1001의 n+1개로 초기화 해준다.
수의 범위가 -1000 <= n <= 1000이기 때문에 그보다 작은 수로 초기화했다.

그리고 점화식을 세워야 한다.

1. 자기 자신이 최대인 경우
2. 이전의 최댓값과 자신을 더한 경우가 최대인 경우

2가지 경우가 있다.

따라서 이 둘을 비교해서 최댓값을 리스트에 넣고 가장 큰 값을 출력하면 된다.