[Algorithm] 백준 1912 연속합 | 파이썬 (DP, Dynamic Programming)

※ 1912 연속합

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

 

문제 해결 TIP

현재값이 큰지, 이전 dp값과 현재값을 더한 값이 큰지 비교해야 한다. dp의 상태는 다음과 같이 변화한다. 최종 dp의 max값을 출력하면 된다.

 

전체 코드

n = int(input())
number = list(map(int,input().split()))
#number = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]

dp = [-10000]*(n+1)
dp[0] = number[0]
for i in range(1,len(number)):
    dp[i] = max(dp[i-1]+number[i],number[i])
print(max(dp))