[백준/BOJ] 백준 코딩 알고리즘 1912번 연속합 Python 다이나믹 프로그래밍

 

나의 풀이

 

이번 문제는 문제의 제목부터 힌트를 주고 있다고 느껴졌다

말 그대로 '연속합'이기 때문에 

현재 포인터가 보고 있는 수 까지에 대해서 연속하는 합과 그렇지 않은 값 (현재값)을 비교하여 최대값을 저장하면 된다

 

이를 간단히 정리하면 다음과 같다

dp[i] = max(i까지의 연속합, 현재값 i)

 

둘 중에 큰 값이 dp 배열에 저장되며,

i까지의 연속합이 크다면, dp[i - 1] 값에 i값이 더해진 값이 dp[i]에 저장되며

현재값 i가 더 크다면, dp[i]에는 i 값이 저장된다 -> 이 말은 지금까지 있던 수를 더하는 것보다, i가 더 크기 때문에 연속이 끊기는 경우를 의미한다.

 

이를 코드로 나타내면 다음과 같다

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))

dp = [0] * N
dp[0] = max(-(sys.maxsize), nums[0])

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

print(max(dp))