[알고리즘] 최대 연속 부분합 구하기: Kadane's 알고리즘

최대 연속 부분합

최대 연속 부분합이란 어떤 수열 $a_1, a_2, ..., a_{N}$이 주어졌을 때 $1 \leq i \leq j \leq N$ 를 만족하는 $sum(a_i, a_{i+1}, ..., a_j)$ 중 최댓값을 뜻합니다.

 

https://www.acmicpc.net/problem/1912

1912번: 연속합

이 문제를 예로 들어봅시다.

쉽게 떠올릴 수 있는 풀이는 어떤 $(i, j)$에 대해 $sum(a_i, a_{i+1}, ..., a_j),(1 \leq i \leq j \leq N)$ 을 $O(1)$로 구할 수 있게끔 전처리 한 뒤, 가능한 모든 $(i, j)$쌍에 대해서 부분합을 구하는 방법입니다.

하지만 이 풀이의 시간 복잡도는 $O(N^2)$ 이므로 $(N \leq 100,000)$인 이 문제에 적용할 수 없습니다.

 

Kadane's 알고리즘

정의

Kadane's 알고리즘은 최대 연속 부분합을 $O(N)$으로 구하는 알고리즘입니다.

간단한 dp를 이용합니다. 정의와 점화식은 다음과 같습니다. 편의상 수열이 0부터 시작한다고 하겠습니다.

 

$D[i]:$ 마지막 원소가 i 번째 원소인 부분 수열의 합 중 최대값

$\begin{cases} D[0] = a_i \\D[i] = max(D[i-1] + a_i,\ a_i),\ (1 \leq i < N)\end{cases} $

 

이를 이용하면 수열 전체에서의 최대 연속 부분합은 $max(D[0], D[1], ..., D[N-1])$ 임을 알 수 있습니다.

 

점화식 유도

제가 형식적인 증명은 못하지만 점화식 유도과정 정도는 알려드릴 수 있습니다.

 

수열의 길이가 4라고 합시다.

D[i]는 마지막 원소가 i 번째 원소인 부분 수열의 합 중 최대값이므로 다음과 같습니다.

 

$\begin{cases}D[0] = max(\ [a_0]\ )\\D[1] = max(\ [a_0+a_1],\ [a_1]\ )\\D[2] = max(\ [a_0+a_1+a_2] ,\ [a_1+a_2],\ [a_2]\ )\\D[3] = max(\ [a_0+a_1+a_2+a_3],\ [a_1+a_2+a_3],\ [a_2+a_3],\ [a_3]\ )\end{cases}$

 

일단 $D[i]$의 정의가 모든 부분 수열에 대한 합을 고려한다는 것은 확실합니다.

 

다음은 점화식을 유도하는 과정입니다.

D[2]에서 마지막 $[a_2]$를 빼고 보면 다음을 알 수 있습니다.

$\begin{eqnarray}D[2] &=&max(\ [a_0+a_1+a_2],\ [a_1+a_2]\ ) \\&=& max(\ [a_0+a_1], [a_1]\ ) + a_2\\ &=& D[1] + a_2\end{eqnarray}$

 

따라서 $D[2] = max(D[1]+a_2,\ a_2)$ 입니다.

 

비슷한 원리로 직접 몇 개 더 해보면, 결국 $D[i]$가 다음과 같음을 알 수 있습니다.

$\begin{eqnarray}D[i] &=& max(\ [a_0 + a_1\text{ + ... + }a_i],\ [a_1\text{ + ... + }a_i],\text{ ..., }[a_{i-1} + a_i],\ [a_i]\ )\\ &=& max(\ max(\ [a_0 + a_1\text{ + ... + }a_{i-1}],\ [a_1\text{ + ... + }a_{i-1}],\text{ ..., }[a_{i-1}]\ ) + a_i,\ [a_i]\ )\\&=& max(\ [D[i-1] + a_i,\ a_i\ )\end{eqnarray}$

 

코드 구현

$D[i]$를 구할 때 직전 단계인 $D[i-1]$ 외에 다른 값을 쓰지 않습니다.

따라서 메모이제이션을 배열로 유지하지 않고 직전의 최대 부분합만 저장해두면 됩니다.

 

위 문제를 Kadane's 알고리즘으로 배열 없이 해결한 코드는 다음과 같습니다.

메모이제이션 값은 val에, 정답은 ans에 저장합니다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int t, n, x;
int main(){
    cin >> t;
    while (t--) {
        cin >> n;
        int ans = -999999999;
        int val = 0;
        for (int i = 0; i < n; i++) {
            cin >> x;
            val = max(val + x, x);
            ans = max(ans, val);
        }
        cout << ans << '\n';
    }
}