왼쪽 후보 4
왼쪽 하위 호출이 찾은 최댓값입니다. 구간은 중앙 오른쪽을 보지 않습니다.
왼쪽 최댓값과 오른쪽 최댓값만 비교하면 중앙 경계를 가로지르는 최적 구간을 놓칠 수 있습니다.
왼쪽 하위 호출이 찾은 최댓값입니다. 구간은 중앙 오른쪽을 보지 않습니다.
오른쪽 하위 호출이 찾은 최댓값입니다. 중앙 왼쪽의 suffix를 포함하지 않습니다.
왼쪽 suffix 4 + -1과 오른쪽 prefix 2 + 1을 합쳐 만듭니다.
병합 계약은 “전체 구간의 최대 부분합”을 반환하는 것입니다. 그래서 하위 답 2개와 중앙 교차 답 1개를 함께 비교해야 계약이 완성됩니다.