겹침 없이 모두 포함
왼쪽과 오른쪽 구간이 빠지거나 중복되지 않도록 시작과 끝 인덱스를 고정합니다.
분할 정복 병합 계약 기준
분할 정복은 작은 문제의 답을 믿고 합치는 방식이라, 분해 범위와 병합 결과의 계약이 어긋나면 바로 오답이 됩니다.
더 쪼갤 수 없는 값 정의
원소 하나, 빈 구간, 길이 0 같은 최소 단위의 반환값을 먼저 확정합니다.
부분 답의 의미를 유지
정렬성, 최대 부분합, 누적 비용처럼 병합 뒤에도 같은 속성이 남아야 합니다.
제출 전 남길 증거
병합 정렬
두 정렬 배열의 남은 꼬리를 빠짐없이 붙였는지 확인합니다.
최대 부분합
왼쪽 답, 오른쪽 답, 가운데 교차 답을 모두 후보로 둡니다.
반복 병합
폭을 두 배로 늘릴 때 마지막 짧은 구간도 병합 대상에 넣습니다.