보통
Maximum Subarray
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 최대부분합(nums):2 현재합 = nums[0]3 최대합 = nums[0]4 반복 i = 1 … n-1:5 현재합 = max(nums[i], 현재합 + nums[i]) // 잇기 vs 새로 시작6 최대합 = max(최대합, 현재합)7 반환 최대합
변수
- i
- 0
- nums[0]
- -2
- 현재합
- -2
- 최대합
- -2
1 / 18첫 칸을 현재합과 최대합의 출발점으로 삼습니다.
매 칸에서 '지금까지 합에 잇기 vs 여기서 새로 시작'을 골라 최대 연속합을 O(n)에 찾는다(Kadane).
왜 헷갈리는가
DP인데 배열(표)이 필요 없어 보인다 — 사실 '직전까지의 최선'만 있으면 되므로 변수 두 개(현재합·최대합)로 압축된다. 원소가 전부 음수일 때 처리도 헷갈린다.
핵심 아이디어
현재합이 음수가 되는 순간, 그 앞부분을 계속 끌고 가는 것은 손해다 — 지금 값에서 새로 시작하는 편이 낫다. 이 한 줄의 판단이 Kadane의 전부다.
매 칸에서 현재합을 갱신하고, 그때그때 최대합과 비교해 기록한다.
복잡도
시간 O(n)·공간 O(1). 브루트포스 O(n²)를 '직전 상태만 기억'으로 접는다.
실무에서 어디에 쓰나
'연속 구간의 최대 누적'은 시계열 분석의 단골이다.
- 매출/수익: 연속된 최고 성과 구간(최대 상승분) 탐지
- 신호 처리: 잡음 속 최대 에너지 연속 구간 찾기
- 이상 탐지: 누적 편차가 가장 큰 연속 윈도우 식별
- 리소스: 부하가 연속으로 몰린 최악 구간 산정
흔한 실수
초깃값을 0으로 두면 '전부 음수'일 때 0을 답으로 내는 버그 → 첫 원소(nums[0])로 초기화.
기억할 것
- 현재합이 음수면 버리는 게 이득.
- DP지만 변수 두 개로 접힌다.
- 초기값은 nums[0](전부 음수 대비).
- 연속 구간 최대 누적의 표준.