> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/dynamic-programming/max-contiguous-subarray-sum.md).

# 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과 첫번째 원소를 비교하여 최댓값을 저장하는 변수가 필요하다.