카데인 알고리즘 (Maximum Subarray Sum)

"연속한 며칠 동안의 주가 등락을 더했을 때 가장 이득이 큰 구간은?" — 정수 배열에서 연속된 부분 배열의 합 중 최댓값을 찾는 문제다. 모든 구간을 다 더해 보면 느리지만, 카데인 알고리즘은 배열을 딱 한 번 훑고 답을 낸다.

1. 소박한 방법은 왜 느릴까

길이 n 배열에서 연속 구간은 시작점 i, 끝점 j를 고르는 경우의 수만큼 있다. 각 구간의 합을 새로 더하면 O(n³), 누적 합을 재활용해도 O(n²). n이 10만이면 100억 번 — 감당이 안 된다.

카데인의 통찰은 이렇다. "지금 위치 i에서 끝나는 최대 구간 합" 하나만 계속 들고 다니면 된다. 이 값을 cur라 하면,

즉 "앞에서 이어온 합에 a[i]를 붙이는 게 나은가, 아니면 여기서 a[i]부터 새로 시작하는 게 나은가?"를 매 칸마다 한 번만 비교한다. 이어온 합이 음수가 되는 순간, 그건 뒤에 뭘 붙여도 짐만 되므로 버리고 새로 시작한다.

2. 한 칸씩 따라가 보기

아래에서 「한 칸 →」를 누르며 진행해 보자. 주황 테두리가 지금 보는 칸, 초록 막대가 현재까지 찾은 최적 구간이다. 막대를 클릭하면 그 칸의 값을 바꿀 수 있다.

3. 코드는 4줄이면 끝난다

def kadane(a):
    best = cur = a[0]
    start = best_l = best_r = 0
    for i in range(1, len(a)):
        if cur + a[i] < a[i]:       # 이어붙이기보다 새로 시작이 낫다
            cur, start = a[i], i
        else:
            cur += a[i]
        if cur > best:               # 최고 기록 갱신
            best, best_l, best_r = cur, start, i
    return best, (best_l, best_r)

루프 한 번, 비교 두 번. 전체가 O(n) 시간, O(1) 공간이다. 구간의 위치까지 알고 싶으면 위처럼 start를 같이 들고 다니면 된다.

4. 왜 이게 맞을까 (귀납)

cur가 항상 "인덱스 i에서 끝나는 구간들 중 최대 합"을 정확히 담는다는 것만 보이면 된다.

• i에서 끝나는 구간은 두 종류뿐이다: (a) a[i] 하나로만 이뤄진 구간, (b) "i-1에서 끝나는 어떤 구간" 뒤에 a[i]를 붙인 것.
• (b)의 최댓값은 "i-1에서 끝나는 최대 구간 합" + a[i] = 이전 cur + a[i].
• 그래서 cur = max(a[i], 이전 cur + a[i]). 전체 정답은 모든 i에 대한 cur의 최댓값, 즉 best.

이건 사실 아주 작은 동적 계획법이다. 상태는 "여기서 끝나는 최대 합" 하나, 점화식은 위의 한 줄.

5. 분할 정복 방법과 비교