백준 1912

n개의 정수로 이루어진 수열이 주어질 때,
1개 이상의 연속된 숫자 합 중 최댓값을 구하는 문제이다.

'dp[i]: i번째 원소까지의, 연속된 부분 합의 최댓값'이라 정의하자.

간단한 예시는 다음과 같다.

nums = [-1, 2, 3, 5, -4]

dp = [-1, 2, 5, 10, 6]

dp[0]은 항상 nums[0]이므로 여기선 -1이다.

dp[1]은..
1번째 원소까지의, 연속된 부분 합의 최댓값인데,
0번째 원소까지의 연속된 부분 합의 최댓값에 nums[1]을 더한 값과,
nums[1]의 값 중 큰 값이 될 것이다.

즉, dp[1] = max(dp[0] + nums[1], nums[1])이다.

일반적인 경우에 대해 조금 더 풀어 설명하면..

예를 들어 (i - 1)번째 원소까지의 연속된 부분 합의 최댓값이 -3이고,
그리고 i번째 원소가 10이라고 하자.

그러면 i번째 원소까지의 연속된 부분 합 중 최댓값이 dp[i]인데,
-3 + 10 = 7이거나 i번째 원소를 선택하지 않은 -3 둘 중 하나일 것이다.

그래서 다음과 같은 점화식을 구할 수 있다.
(다이나믹 프로그래밍은 곧 점화식!)

dp[i] = max(dp[i - 1] + nums[i], nums[i])

코드(정답)는 다음과 같다.

# 1912

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

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

# print(dp)
print(max(dp))