왼쪽 하위 호출이 이미 찾은 최대 부분합을 후보로 둔다.
병합 판단
최대 부분합 후보 비교
하위 구간의 최댓값만 믿으면 중앙을 가로지르는 답을 놓친다. 병합 단계는 세 후보를 같은 기준으로 계산해 최종 구간 계약을 만든다.
mid에서 왼쪽 suffix와 오른쪽 prefix를 각각 확장해 더한다.
오른쪽 하위 호출의 최댓값을 같은 기준으로 비교한다.
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
정답 6은 중앙을 지나가는 [4, -1, 2, 1]에서 만들어진다.
구현 점검
suffixmid에서 왼쪽으로 누적
prefixmid + 1에서 오른쪽으로 누적
compare세 후보 중 최댓값 반환