[백준] 1912: 연속합 - 동적 계획법

다른 코드 참조: X, 푼 횟수: 5

풀이과정

연속되는 구간의 합의 최대를 구하면 되는 문제로 다음과 같이 생각할 수 있다.

1. num(i): i번째 숫자, s = i번째까지의 최대 합

2. num(i) < 0 일 경우 3가지의 경우를 생각해 볼 수 있다.

2 - i. s + num(i) < 0

num(i+1)부터 다시 시작하는 게 더 크다. 하지만 num(i) 이후의 연속구간의 최대합과 num(i) 이전의 연속구간의 최대합도 비교를 해야 하므로 num(i) 이전 연속구간의 최대합을 저장하고 s = 0으로 초기화한다.

2 - ii. num(i) < 0

num(i)를 더한 채로 계속 더하는 연속구간의 합과 num(i) 이전의 연속구간의 최대 합을 비교한다.

2 - iii. num(i) > 0

계속 커지므로 부담없이 더한다.

 

코드

import sys

n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
m = -1000*n
cnt = 0
s = 0

for i in range(n):
    if num[i] >= 0: s += num[i]
    else:				#num[i] < 0 인경우
        cnt += 1			#음수의 수를 카운팅 해준다.
        m = max(m, s)			#저장된 최대합과 num[i] 이전의 연속구간 최대합인 s의 크기중 큰걸 저장한다.
        				#m보다 작은 크기는 잊어버려도 되므로 저장을 안해도 된다.
        if s + num[i] < 0: s = 0	#s를 0으로 초기화 해준다
        else: s += num[i]
m = max(m, s)


if cnt == n:
    m = max(num)			#num이 모두 음수인 경우 제일 큰 음수를 출력한다.
print(m)