연속된 subarray중에 합이 제일 큰 것을 찾아라. (+/- 섞여 있음)
2~8까지가 정답.
O(n^3) : 쉬움
연속된 모든 subarray 경우를 다 해본다.
n개 중 점 2개를 찍는 방법
O(n^2) : Prefix Sum
n^2개의 영역을 잡는 것은 같다.
하지만 합을 계산할 때 앞을 보고 계산하는 것이 아니라 미리 계산해둔 결과의 차를 이용한다.
* 답으로 zero개의 배열을 허용할 것인가? 에 따라서 답이 다르다.
최소 하나를 포함해야 한다면 -1이 정답이지만
크기가 0인 배열을 허용한다면 정답은 0임.
풀이는 비슷하지만 전혀 다른 문제가 된다.
O(n) : zero허용한다고 가정
모든 자리에서 끝나는 가장 좋은 답(가장 합이 큰 것 찾기)
사이즈 0 허용하므로 칸이 아니라 경계에서 끝난다고 생각하자
x가 가장 좋은 답인 상태에서
y에서 끝나는 가장 좋은 답을 찾아야 한다.
y를 무조건 포함해야 한다면 x+y가 가장 좋은 답
(x의 시작부분을 움직여서 더 좋은 답을 만들 수 없으므로)
1. x+y >0(양수)일때,
x+y > y => x+y 더 큰 값이 나오기 때문에 정답 (2개 이상을 포함하는 정답 중 가장 좋음)
x+y < y => y (1개 이상을 포함하는 정답 중 가장 좋음)
2. x+y <0(음수)일때, 차라리 아무것도 포함하지 않는 0이 정답
밑에는 0개를 고려하지 않았을 때. 전체 답은 달라지지 않지만 중간 결과가 다를 수 있다.
i번째(경계 아니라 그 자리)에서 두 가지 값을 계산한다.
1. i번째 element를 반드시 포함하는 최대 (1번 값에서 붙인다. or 혼자만 쓴다.)
3 -2 2 6 4 7 1 9
2. i번째 element를 반드시 포함하지 않아도 되는 최대
3 3 3 6 6 7 7 9 (1번째에서 본 것중에 가장 큰 것..?)
* 다른 방법 *
prefix sum을 계산하고 min(prefix sum)을 뺸다.
쉽지만 3번돌아야 함. (prefix/prefix minimum/ 빼기)
