카데인 알고리즘의 수학적 증명

1. 전체 탐색 공간의 분할 (Partitioning)

길이가 $n$인 배열 $A$에서 만들 수 있는 연속 부분 배열의 개수는 총 $\frac{n(n+1)}{2}$개입니다.

이 전체 부분 배열들의 집합을 "어느 인덱스에서 끝나는가?"를 기준으로 $n$개의 서로소 부분집합(Disjoint Sets)으로 나눕니다.

• $S_0$: 인덱스 $0$에서 끝나는 부분 배열들의 집합
• $S_1$: 인덱스 $1$에서 끝나는 부분 배열들의 집합
• $\dots$
• $S_j$: 인덱스 $j$에서 끝나는 부분 배열들의 집합 ($0 \le j < n$)

모든 연속 부분 배열은 반드시 $0$부터 $n-1$ 중 단 하나의 끝점을 가지므로, 전체 부분 배열 중 최대합(전역 최적해)은 각 집합의 최댓값들 중 가장 큰 값과 같습니다.

$\text{Global Max} = \max_{0 \le j < n} \Big( \max(S_j) \Big)$

---

2. 점화식의 수학적 유도 (최적 부분 구조)

이제 문제를 "$j$번째 원소로 끝나는 부분 배열 중 최대합 $M[j]$를 어떻게 구할 것인가?"로 좁힐 수 있습니다.

수학적으로 $M[j]$는 다음과 같이 정의됩니다.

$M[j] = \max_{0 \le i \le j} \sum_{k=i}^j A[k]$

이 식에서 시작 인덱스 $i$의 경우의 수를 $i = j$인 경우(원소 1개짜리)와 $i < j$인 경우(길이가 2 이상인 경우)로 분리합니다.

$M[j] = \max \left( A[j],\; \max_{0 \le i \le j-1} \left( \sum_{k=i}^{j-1} A[k] + A[j] \right) \right)$

여기서 $A[j]$는 $i$와 무관한 공통 덧셈 상수이므로 밖으로 묶어낼 수 있습니다.

$M[j] = \max \left( A[j],\; \left( \max_{0 \le i \le j-1} \sum_{k=i}^{j-1} A[k] \right) + A[j] \right)$

괄호 안의 $\max_{0 \le i \le j-1} \sum_{k=i}^{j-1} A[k]$는 정확히 이전 단계의 정의인 $M[j-1]$입니다.

따라서 다음과 같은 전형적인 동적 계획법의 점화식이 도출됩니다.

$M[j] = \max(A[j],\; M[j-1] + A[j])$

식을 $A[j]$를 기준으로 정리하면 더욱 직관적인 형태가 됩니다.

$M[j] = A[j] + \max(0,\; M[j-1])$

• $M[j-1] > 0$이면: 이전 누적합을 붙이는 것이 이득이므로 $M[j-1] + A[j]$ 선택
• $M[j-1] \le 0$이면: 이전까지의 최적합이 음수이므로, 이전 기록을 버리고 $A[j]$ 단독으로 새로 시작하는 것이 무조건 이득

---

3. 메모리 최적화 ($O(N) \to O(1)$ 공간)

점화식 $M[j] = \max(A[j], M[j-1] + A[j])$를 보면, $M[j]$를 계산할 때 필요한 이전 값은 오직 직전 값인 $M[j-1]$ 하나뿐입니다. $M[j-2], M[j-3]$ 등 그 이전의 값들은 알 필요가 없습니다.

따라서 $N$ 크기의 배열 $M[\ ]$을 메모리에 유지할 필요 없이, 단 하나의 변수(currentSum)만 계속 덮어쓰면서 갱신하면 충분하므로 공간 복잡도가 $O(1)$이 됩니다.