Max Contiguous Subarray Sum

문제 복기

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

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

입력 : 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력 : 첫째 줄에 답을 출력한다.

Ex1) I : 10 10 -4 3 1 5 6 -35 12 . 21 -1 O : 33 Ex2) I : 10 2 1 -4 3 4 -4 6 . 5 -5 1 O : 14 Ex3) I : 5 -1 -2 -3 -4 -5 O : -1

알고리즘 생각

1. sum에 a[i]를 더할지

2. 안 더하고 a[i]부터 다시 시작

3. a[i-1]까지의 합

생각의 오류

1,2는 Math.max(sum+a[i],a[i])로 구현했지만, a[i-x]부터 a[i] 혹은 a[i-x]부터 a[i-1]까지의 합이 정답이 될 수도 있다. 그렇기 때문에 sum값이 갱신 되기 전에 그 전의 sum값을 저장하는 변수가 필요하다! 저장할 뿐만 아니라 sum과 최댓값을 비교해서 저장해야한다!

예제 1번에서 정답은 33이 되어야하는데 알고리즘 1,2번만 고려한 Math.max(sum+a[i],a[i]) = Math.max(33-1,-1) = 32가 되어 오답이 되어버린다. 그래서 이전의 sum값을 저장하는 변수가 필요하다.

예제 3번에서 배열은 갈수록 감소하는 배열이기 때문에 제일 첫번째 원소가 곧 최대합이 된다. sum은 sum대로 더할지, 다시 시작할 Math.max(sum+a[i],a[i])로 비교하고, 이 sum과 첫번째 원소를 비교하여 최댓값을 저장하는 변수가 필요하다.