[Python] 백준 1912 "연속합_동적계획법" 문제풀이

문제풀이

import sys

input = sys.stdin.readline
n = int(input())

num = list(map(int,input().split()))
dp = [-1001]*(n+1)
dp[0]=num[0]
for i in range(1,n+1):
    if dp[i-1]<0:
        dp[i]=num[i]
    else:
        dp[i]=dp[i-1]+num[i]
        
print(max(dp))

피드백

 

dp[i-1] 값이 0보다 작으면 dp[i]=num[i] 를 0보다 크면 dp[i]=dp[i-1]+num[i] 를 해준다.

dp 리스트 중 가장 큰 값을 출력해준다.