문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
문제에서 나온 예시로 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌을 때, 여기서 정답은 12+21인 33이 정답이 된다.
해당 문제에서 주목해야 할 점은 연속된 몇 개의 수와 구할 수 있는 합 중 가장 큰 합이다. 그럼 연속된 몇 개의 수는 어떻게 구해야 하는가? 일단은 계속 배열을 돌아가면서 최대한 큰 수를 만들 수 있도록 해야 하는데 이를 기록하고 가장 큰 값을 도출해내기 위해선 동적 계획법을 통해 풀어야 함을 알았다.
그렇다면 동적 계획법에서 중요한 것은 점화식인데, 어떤 식으로 점화식을 도출해 낼까? 일단 우리에게 주어지는 것은 n의 정보와 수열의 정보이다. 이를 가지고 연속된 수 중에 가장 최대한 큰 수를 계속 기록하기 위해서는 수열이 배열이라는 가정 하에 생각해보면 된다. 배열을 처음부터 끝까지 돌면서 우리는 연속된 수들을 만날 것이다. 이 연속된 수에서 우리는 기존의 누적된 값을 현재 보고 있는 값과 비교해야 한다. 여기서 중요한 점은 무조건 음수라고 해서 거기서 끊어야 하는게 아닌, 음수라고 하더라도 그 뒤에 연속되는 값을 더했을 때 가장 큰 수가 된다면 음수라도 포함할 수 있는 경우를 생각해야 한다. 그렇다면 점화식은 이전까지 누적된 값과 현재 보고 있는 값을 더했을 때와 현재 값 중에 더 큰 값을 골라야 한다.
dp[n] = max(dp[n-1] + arr[n], arr[n])