[백준][DP] 1912번 연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1912)

풀이

처음에는 문제를 보고 난해하다 생각했습니다.(*^^*) 일부 연속된 수를 합해서 최대의 수를 만들어야했는데 음수가 과연 포함될 수 있을지에 대한 고민이 들었습니다. 그냥 생각해보면 음수가 더해지면 작아지니까 아닐 것 같았는데 생각해보니 100 -1 100 이라는 경우엔 세개 다 더하는 경우가 최대의 합이니까 더해지는 게 맞습니다! 어떻게 구현할 지도 처음에는 약간 헷갈렸는데 dp[i]는 i번째 수열까지 연속된 가장 큰 합을 저장하도록 합니다. 그럼 dp[i+1]이 됐을 때는 dp[i]에다가 i+1번째 수를 더한 값이 자기 자신(i+1의 값)보다 더 크면 더하고, 만약  작아진다면 가장 큰 합이 될 수 없으므로 그 자리에서 부터 만들 수 있는 가장 큰 합인 i+1부터 다시 시작합니다.

코드

https://github.com/kswim/Algorithm/blob/master/DP/1912.cpp