CodeDrive

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12 + 21 인 33이 된다.

DP를 활용해서 푸는 문제이다. 반복문은 여러개 써야 할 것 같지만 배열 한 번을 탐색하는 반복문 하나로도 풀 수 있다. 정답을 maxsum이라 하고 초기값을 -1000으로 잡아준다. 왜냐하면 모든 수는 -1,000보다는 크기 때문이다. 배열중 임의의 값과 그 전부터 누적해온 값 중 더 큰 값을 선택하고 이를 maxsum과 비교해서 maxsum보다 커지는 값들이 있다면 그 값을 maxsum으로 갱신해준다.

예시 케이스로 설명하면 다음과 같이 된다.

처음에는 max(10,0+10)이므로 temp가 10이 되고 maxsum은 당연히 10으로 최신화된다.

그 다음에는 max(-4,10-4)이므로 temp가 6이 되지만 maxsum은 유지된다.

max(3,6+3)이므로 temp가 9가 되지만 maxsum은 유지된다.

max(1,9+1)이므로 temp가 10이 되지만 maxsum은 유지된다.

max(6,10+6)이므로 temp가 16이 되고 maxsum이 16이 된다.

max(-35,16-35)이므로 temp가 -19가 되고 maxsum은 유지된다.

max(12,-19+12)이므로 temp가 12가 되고 maxsum은 유지된다.

max(21,12+21)이므로 temp가 33이 되고 maxsum은 갱신된다.

max(-1,33-1)이므로 temp가 32가 되고 maxsum은 유지된다.

따라서 12+21인 33이 정답이 된다.