백준 1912 : 연속합 (Python)

본문 링크

N=int(input())

dp=list(map(int,input().split()))

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

print( max (dp) )

📌 어떻게 접근할 것인가?

연속한 어떤 수들의 합중 가장 큰 값을 구하는 문제이다.

아주 기초적인 $DP$ 문제라고 느껴졌다.

$DP$ 배열을 입력받고 DP[i]는 DP[i]와 DP[i-1]+DP[i] 값중 더 큰 값을 가지도록 한다.

즉 음수인 값은 알아서 뛰어넘게 되고 양수끼리만 더하게 된다.

이후 양수끼리만 더해진 값들의 $DP$ 리스트 에서 가장 큰 값을 출력한다.