[백준]1912번 연속합 - DP

 

n = int(input())

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

dp = [0] * n
dp[0] = num[0]
for i in range(1, n):
    dp[i] = max(dp[i - 1] + num[i], num[i])  # 직전수+현재수와 현재수를 비교해 큰것을 저장
print(max(dp))

 

코드 설명

먼저 n이 1인 경우를 대비해 dp[0]에는 num[0] 값을 넣어준다.

반복문을 통해 직전수+현재수 vs 현재수 중 큰 값을 저장시키면서 반복한다.

저장된 값중 가장 큰 값을 출력하면 연속합중 가장 큰 값을 구할 수 있다.

 

Point : 큰 값을 저장시키기 위해서 직전까지 누적된 합과 현재의 수를 비교하여 큰 것을 저장한다.

이 과정을 진행하는 이유는 직전까지의 누적 합보다 현재의 수 자체가 더 큰 경우가 있으므로 그 결과를 반영하기 위함이다.

처음에는 직전 누적합과 직전 누적합+현재합을 비교하는 큰 값을 저장하는 방식으로 설계 하였는데 이 경우에는 바로 위의 경우를 반영할 수 없었다. 따라서 직전까지의 누적합과 현재의 수 중 큰 값을 저장하는 방식으로 바꾸었다. (현재 수 자체가 더 큰 경우 더한 값을 초기화 시켜주기 위함)