[Python] 백준 1912_ 연속합

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

이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.

1. DP정의

• dp: i번째 이전의 어느 특정 시점부터 i번째까지 더했을때의 합의 최대값
• max_n: 특정시점부터 특정 시점까지의 연속합의 최대값
• d[0] = num[0]
• max_n = num[0]으로 설정하고 시작한다.

(예제)
10
2 1 -4 3 4 -4 6 5 -5 1

2. 점화식 찾기

d[i] = max(d[i-1]+d[i], d[i])
이렇게 하면, num이 음수가 나오도 자동으로 처리된다.

(맨 처음 점화식을 d[i] =max(d[i-1]+d[i], 0) 으로 세웠었다. 연속합이 최대로 크지 않다면 0으로 세팅해주고 그 뒤부터 다시 합을 구해야된다고 생각했다. 하지만 이렇게 구현하면 문제의 예제들은 통과할 수 있지만, 반례 n=3/ num=[-3, -2, -1] 에서 다른 답(0)이 나온다. 음수에 대하여 제대로 처리가 안되기 때문이다. )
올바른 점화식을 이용하면, 반례 n=3/ num=[-3, -2, -1]에서도 정답을 찾을 수 있다.

3. 코드

import sys
input = sys.stdin.readline

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

#dp정의
d = [0]*n
max_n = num[0] #처음 값으로 Max값 임의 설정

for i in range(n):   
    if i ==0:
        d[0] =num[0]
    else:
        d[i] = max(d[i-1]+num[i],num[i])

    if max_n<d[i]:
        max_n=d[i]
        
print(max_n)