1912 연속합

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N = int(read())
graph= list(map(int,read().split()))

dp_table = [0] * N
maximum_value = -1e9

dp_table[0] = graph[0]
maximum_value = max(dp_table[0], maximum_value)

for i in range(1,N):
    dp_table[i] = max(graph[i]+dp_table[i-1],graph[i])
    maximum_value = max(dp_table[i],maximum_value)
print(maximum_value)

3. 문제 풀이

점화식을 세우는게 가장 중요하다. 그리고 이 문제는 진행 과정중 maximum 값을 항상 저장해야한다. 왜냐하면, 언제 어디서 maximum 값이 나올지 모르기 때문이다. 점화식은 간단한 편인데, 내가 너무 어렵게 생각해서 문제를 틀렸다ㅠ..

정말 간단하게 이전까지 연속으로 더해진 값을 dp table에 넣되, 현재의 단일 값보다 단일 값 + dp table의 값이 작으면, 연속합보다 단일 값이 더 값이 큰 것이므로 연속을 깨주면 된다. 이를 점화식으로 풀면 다음과 같다.

\[dp\_table[i] = max(graph[i]+dp\_table[i-1], \\graph[i])\]

그리고 maximum 값을 따로 dp값과 비교하여 매번 저장해준다.